Basic solutions of standard-form polyhedra via basis columns
ProvedLinearOptimization.lp_standard_form_basic_ifflinear-programmingpolyhedrasimplex
(Theorem 2.4) Consider the constraints and and assume that the matrix has linearly independent rows. A vector is a basic solution if and only if we have , and there exist indices such that:
- (a) The columns are linearly independent;
- (b) If , then .
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_BasicSolution open Matrix /-- **B&T Theorem 2.4 (p. 53).** Characterization of basic solutions of the standard-form system: under the book's explicit hypothesis that the rows of `A` are linearly independent, `x` is a basic solution iff `Ax = b` and the nonzero coordinates of `x` live inside some basis `B` (injective basic indices with linearly independent basic columns). -/
Formal statement
theorem LinearOptimization.lp_standard_form_basic_iff {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (hA : LinearIndependent ℝ (fun i => A i))
(x : Fin n → ℝ) :
IsBasicSolution (stdFormSystem A b) x ↔
A.mulVec x = b ∧ ∃ B : Fin m ↪ Fin n, IsStdBasis A B ∧
∀ j, j ∉ Set.range B → x j = 0 := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 2.4, p. 53