Fourier–Motzkin elimination computes the projection
ProvedLinearOptimization.fourier_motzkin_projectionfourier-motzkingeometrylinear-programmingpolyhedraprojection
(Theorem 2.10, GOAL) The polyhedron constructed by the elimination algorithm is equal to the projection of , where for ,
Preamble
import Definitions.Def_FourierMotzkinStep /-- **Bertsimas & Tsitsiklis, Theorem 2.10 (p. 73).** One Fourier–Motzkin elimination step computes exactly the projection of the polyhedron onto its first `n` coordinates. -/
Formal statement
theorem LinearOptimization.fourier_motzkin_projection {m n : ℕ}
(A : Matrix (Fin m) (Fin (n + 1)) ℝ) (b : Fin m → ℝ) :
fourierMotzkinEliminate A b =
(fun x : Fin (n + 1) → ℝ => fun l : Fin n => x l.castSucc) ''
polyhedron A b := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 2.10, p. 73
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For every real matrix and , the theorem asserts a set equality: the Fourier–Motzkin elimination set of equals the image of the polyhedron under the coordinate projection dropping the last coordinate. Here the elimination set is such that (i) every row with last coefficient satisfies , and (ii) for every pair of rows with and , (real division; by-zero would give , but the sign conditions preclude that here). Both inclusions are asserted, for all including .
Human review
Confirmed by the mission captain (proposal self-audit).