Skip to main content

Module basis

Module basis 

Source
Expand description

§Chapter 5.1 — Basis columns

§Purpose

The simplex method never forms its basis matrix B explicitly: B is a list of m references into the computational form [A | ±I]. This chapter fixes how the factorization receives that list, so that the simplex (Chapter 6) can call crate::LuFactor::factorize with its basis heading and the constraint matrix A, without copying a column.

The factorization reads B through the trait ColumnSource (the contract’s name): the pair (&[ColumnRef], &CscMatrix) of the simplex is one source, a square CscMatrix (B given explicitly) another. The trait is used by static dispatch only — factorize is generic in the source and the visitor of the entries is a generic closure — so the load of the factorization (step L1) costs what it cost in the first edition, where it was hard-wired to the pair.

§Notation

A ∈ R^{m×n} is a CscMatrix. The basis is B = [b_0 | … | b_{m−1}], and k ∈ 0..m is the position of a basic variable (the index of x_B it occupies). Each column is either

  • structural, b_k = a_j = A e_j (ColumnRef::Structural), or
  • logical, b_k = σ e_i with σ ∈ {+1, −1} (ColumnRef::Logical) — the column of the slack of row i; the sign lets the simplex use either convention (A x − s = 0 gives σ = −1, A x + s = b gives σ = +1).

Positions and rows are different index spaces even though both range over 0..m: FTRAN maps a vector indexed by rows to one indexed by positions, BTRAN the other way round (Chapter 5.4).

§Invariants

(B1) Structural indices are < n, logical rows are < m, and A has exactly m rows; checked by ColumnSource::validate, which crate::LuFactor::factorize calls first, reporting a violation as crate::LuError::Structure. Repeated references (the same column twice) are not an input error: they make B singular, which the factorization diagnoses.

§References

Maros (2003), §5.1 (computational form and logical variables); Koberstein (2005), §2.2.

Enums§

ColumnRef
A column of the basis: a structural column of A or a logical σ e_i.
Sign
Sign σ of a logical column σ e_i.

Traits§

ColumnSource
Where the factorization reads the columns of B from (the contract’s ColumnSource). Static dispatch only: crate::LuFactor::factorize is generic in the source, and ColumnSource::for_each_entry takes a generic visitor.