Reduced-cost optimality conditions
ProvedLinearOptimization.simplex_reduced_cost_optimalitylinear-programmingoptimalityreduced-costsimplex
(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 .
Preamble
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. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 3.1, p. 86
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.