Finiteness of basic solutions
ProvedLinearOptimization.lp_basic_solutions_finitegeometrylinear-programmingpolyhedra
(Corollary 2.1) Given a finite number of linear inequality constraints, there can only be a finite number of basic or basic feasible solutions.
Preamble
import Mathlib.Data.Set.Finite.Basic import Definitions.Def_BasicSolution /-- **B&T Corollary 2.1 (p. 52).** A finite family of linear constraints admits only finitely many basic solutions, and hence only finitely many basic feasible solutions. -/
Formal statement
theorem LinearOptimization.lp_basic_solutions_finite {ι : Type} [Fintype ι] {n : ℕ}
(C : ι → LinearConstraint n) :
{x | IsBasicSolution C x}.Finite ∧
{x | IsBasicFeasibleSolution C x}.Finite := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 2.1, p. 52