One Fourier–Motzkin elimination step produces a polyhedron
ProvedLinearOptimization.fourier_motzkin_eliminate_is_polyhedronlinear-programmingoptimizationpolyhedra
For a system of linear inequalities in variables, perform one Fourier–Motzkin elimination step on the last variable. The retained zero-coefficient rows and every compatible positive/negative row pair form a finite system of inequalities in the first variables. Consequently, there exist a natural number , a matrix , and a vector such that
This theorem records the finite polyhedral presentation produced by one elimination step and is the reusable bridge from Theorem 2.10 to Corollary 2.4.
Formalization Note The row type of the new system is the finite disjoint union of zero-coefficient rows and pairs consisting of a positive-coefficient row and a negative-coefficient row.
Preamble
import Definitions.Def_FourierMotzkinStep
Formal statement
theorem LinearOptimization.fourier_motzkin_eliminate_is_polyhedron {m n : ℕ}
(A : Matrix (Fin m) (Fin (n + 1)) ℝ) (b : Fin m → ℝ) :
∃ (m' : ℕ) (A' : Matrix (Fin m') (Fin n) ℝ) (b' : Fin m' → ℝ),
fourierMotzkinEliminate A b = polyhedron A' b' := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, §2.8 Elimination algorithm pp. 71–72 and Theorem 2.10 p. 73; finite-presentation consequence used in Corollary 2.4 p. 74