The integer hull is finitely generated
ProvedLinearOptimization.integer_hull_is_finitely_generatedconvex-geometryinteger-programmingpolyhedra
Let be a nonempty rational polyhedron presented by an integer matrix and integer vector , and let . Then the integer hull is finitely generated: there are finite families and such that
This is the finite-generation core of Meyer’s theorem. It isolates the integer-lattice argument from the reusable Minkowski–Weyl converse that every finitely generated set is a polyhedron.
Formalization Note. “Finitely generated” is the predicate LinearOptimization.IsFinitelyGenerated, using the finite-generator representation of Bertsimas–Tsitsiklis Eq. (4.6).
Preamble
import Mathlib.Analysis.Convex.Hull import Definitions.Def_LinearOptimization_LagrangeanDual import Definitions.Def_LinearOptimization_FinitelyGeneratedSet open Matrix
Formal statement
theorem LinearOptimization.integer_hull_is_finitely_generated {m n : ℕ}
(D : Matrix (Fin m) (Fin n) ℤ) (d : Fin m → ℤ)
(hfeas : (polyhedron (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))).Nonempty) :
IsFinitelyGenerated
(convexHull ℝ
(lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ)))) := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 11.3, p. 496; proof outline in Exercise 11.8(a)–(d), p. 525; finite-generator form Eq. (4.6), p. 182