Finite integer generators for an integer polyhedron
ProvedLinearOptimization.integer_polyhedron_points_natGeneratedgordan-lemmainteger-programminglinear-optimization
Let and , and let . There are finitely many base points and finitely many directions such that
The statement also covers by allowing . It is the finite integer-generator form used in the proof that the integer hull is a polyhedron.
Preamble
import Mathlib.GroupTheory.Finiteness import Mathlib.Algebra.Group.Submonoid.Finsupp import Mathlib.Tactic import Definitions.Def_LinearOptimization_LagrangeanDual
Formal statement
theorem LinearOptimization.integer_polyhedron_points_natGenerated {m n : ℕ}
(D : Matrix (Fin m) (Fin n) ℤ) (d : Fin m → ℤ) :
∃ (k r : ℕ) (x : Fin k → (Fin n → ℝ)) (w : Fin r → (Fin n → ℝ)),
lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i ↦ (d i : ℝ)) =
{y | ∃ (i : Fin k) (q : Fin r → ℕ),
y = x i + ∑ j, (q j : ℝ) • w j} := by sorrySource
Bertsimas and Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), Theorem 11.3, p. 496, proof outlined in Exercise 11.8(a)-(d), p. 525, especially part (c). The all-cases homogenized formulation is obtained via Gordan finite generation of the nonnegative integer solution monoid.