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_iwithσ ∈ {+1, −1}(ColumnRef::Logical) — the column of the slack of rowi; the sign lets the simplex use either convention (A x − s = 0givesσ = −1,A x + s = bgivesσ = +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§
- Column
Ref - A column of the basis: a structural column of
Aor a logicalσ e_i. - Sign
- Sign
σof a logical columnσ e_i.
Traits§
- Column
Source - Where the factorization reads the columns of
Bfrom (the contract’sColumnSource). Static dispatch only:crate::LuFactor::factorizeis generic in the source, andColumnSource::for_each_entrytakes a generic visitor.