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