The integer hull is a polyhedron
ProvedLinearOptimization.integer_hull_is_polyhedron(Theorem 11.3 — Bertsimas & Tsitsiklis, p. 496.) We assume that the system of linear inequalities has a feasible solution, and that the matrix and the vector have integer entries. Let
Then , the convex hull of , is a polyhedron.
import Mathlib.Analysis.Convex.Hull
import Definitions.Def_LinearOptimization_LagrangeanDual
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 11.3 (p. 496).** The convex hull of the integer points
of a polyhedron with integer data is a polyhedron: if `Dx ≥ d` is
feasible and `D`, `d` are integer, then `CH({x integer | Dx ≥ d})` equals
`{x | Fx ≥ f}` for some finite real system `(F, f)`. -/
theorem LinearOptimization.integer_hull_is_polyhedron {m n : ℕ}
(D : Matrix (Fin m) (Fin n) ℤ) (d : Fin m → ℤ)
(hfeas : (polyhedron (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))).Nonempty) :
∃ (k : ℕ) (F : Matrix (Fin k) (Fin n) ℝ) (f : Fin k → ℝ),
convexHull ℝ
(lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))) =
polyhedron F f := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix an integer matrix and integer vector , cast to , and assume the real polyhedron is nonempty (note: nonemptiness of the real polyhedron, not of its integer points). Let be its set of integer points. The conclusion asserts there exist a natural number , a real matrix , and such that the convex hull of over equals (componentwise ) — i.e. the integer hull is again a finitely-constrained polyhedron of the same inequality form. Edge cases the quantifiers admit: if , its hull is , which is representable (e.g. , , ); would represent all of ; no bound on and no rationality/integrality of is claimed, only real entries.
Confirmed by the mission captain (proposal self-audit).