The integer hull is a polyhedron
ProvedLinearOptimization.integer_hull_is_polyhedronconvex-hullinteger-hullinteger-programmingpolyhedra
(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.
Preamble
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)`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 11.3, p. 496