Reduced-cost optimality conditions
ProvedLinearOptimization.simplex_reduced_cost_optimality(Theorem 3.1) Consider a basic feasible solution associated with a basis matrix , and let be the corresponding vector of reduced costs.
- (a) If , then is optimal.
- (b) If is optimal and nondegenerate, then .
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_Polyhedron import Definitions.Def_LinearOptimization_ReducedCost open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 3.1 (p. 86).** Reduced-cost optimality conditions at a basic feasible solution `x` associated with the basis `B`: (a) if every reduced cost is nonnegative, `x` is optimal; (b) if `x` is optimal and nondegenerate, every reduced cost is nonnegative. -/
theorem LinearOptimization.simplex_reduced_cost_optimality {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hA : LinearIndependent ℝ (fun i => A i))
(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) :
((∀ j, 0 ≤ reducedCost A c B j) → IsLpOptimal c (stdPolyhedron A b) x) ∧
(IsLpOptimal c (stdPolyhedron A b) x →
¬IsStdDegenerateBasicSolution A b x →
∀ j, 0 ≤ reducedCost A c B j) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Let be a real matrix with linearly independent rows, , ; let select linearly independent columns of ; let satisfy , , and for every outside the range of . Writing for the reduced cost, the theorem asserts a conjunction. (a) If for every (basic columns included), then is a minimizer of over . (b) Conversely, if is such a minimizer and is not std-degenerate — where std-degenerate means: is a basic solution of the standard-form constraint system (equalities plus signs ) and strictly more than coordinates of vanish ( = truncated natural subtraction) — then for every . Note that the non-degeneracy proviso in (b) is a negation of a conjunction: it holds in particular whenever fails to be a basic solution of the standard-form system.
Confirmed by the mission captain (proposal self-audit).