A simplex pivot yields a new basic feasible solution with lower cost
ProvedLinearOptimization.simplex_pivot_basis_changebasislinear-programmingpivotingsimplex
(Theorem 3.2) In the setting of a simplex iteration — a nondegenerate basic feasible solution with basis matrix , a nonbasic index with , the th basic direction,
finite and attained at the index (so ), and obtained from by replacing with (Eqs. (3.3)–(3.4)):
- (a) the columns , , and are linearly independent and, therefore, is a basis matrix;
- (b) the vector is a basic feasible solution associated with the basis matrix .
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 3.2 (p. 89).** Basis change at a simplex pivot: with entering index `j` (`c̄_j < 0`), exiting row `ℓ` attaining the ratio test, and `B'` obtained from `B` by replacing `B(ℓ)` with `j`, the new basic columns are linearly independent (so `B'` is a basis matrix), and `y = x + θ* • d` is a basic feasible solution associated with `B'`. -/
Formal statement
theorem LinearOptimization.simplex_pivot_basis_change {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hA : LinearIndependent ℝ (fun i => A i))
(B B' : Fin m ↪ Fin n) (hB : IsStdBasis A B)
(x : Fin n → ℝ) (hx : x ∈ stdPolyhedron A b)
(hxB : ∀ j ∉ Set.range B, x j = 0)
(hnd : ¬IsStdDegenerateBasicSolution A b x)
(j : Fin n) (hj : j ∉ Set.range B) (hcj : reducedCost A c B j < 0)
(ℓ : Fin m) (hℓ : 0 < pivotColumn A B j ℓ)
(hmin : ∀ i, 0 < pivotColumn A B j i →
x (B ℓ) / pivotColumn A B j ℓ ≤ x (B i) / pivotColumn A B j i)
(hB'ne : ∀ i, i ≠ ℓ → B' i = B i) (hB'ℓ : B' ℓ = j) :
IsStdBasis A B' ∧
x + (x (B ℓ) / pivotColumn A B j ℓ) • basicDirection A B j ∈
stdPolyhedron A b ∧
∀ k ∉ Set.range B',
(x + (x (B ℓ) / pivotColumn A B j ℓ) • basicDirection A B j) k = 0 := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 3.2, p. 89
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.