Theorem 8 (printed “Theorem 9”) — a lattice-free polyhedron vanishes after Chvátal closures
ProvedCookSensitivity.ChvatalRank.chvatalIter_eq_empty_of_no_integer_pointchvatal-rankcutting-planesinteger-programmingp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a rational polyhedron containing no integral vector, . Then the -th Chvátal closure of is empty:
The result is due to Cook, Coullard and Turán; it bounds the Chvátal rank of lattice-free polyhedra by a function of the dimension alone, and is used in the proofs of Corollary 9 and Theorem 10.
Formalization Note The page prints this result as "Theorem 9"; it is the paper's Theorem 8 (the proofs of Corollary 9 and Theorem 10 cite it as Theorem 8). "Polyhedron" is IsPolyhedron (finitely many rational inequalities); the iteration count is n ^ (2 * n) * 2 ^ (n ^ 3) in ℕ.
Preamble
import Mathlib import Definitions.Def_CookSensitivity_ChvatalRank_IntegerProgram import Definitions.Def_CookSensitivity_ChvatalRank_ChvatalClosure
Formal statement
namespace CookSensitivity.ChvatalRank
open Matrix
theorem chvatalIter_eq_empty_of_no_integer_point {n : ℕ} (P : Set (Fin n → ℚ))
(hP : IsPolyhedron P) (hPZ : ∀ x ∈ P, ¬ IsIntegral x) :
chvatalIter (n ^ (2 * n) * 2 ^ (n ^ 3)) P = ∅ := by sorry
end CookSensitivity.ChvatalRank
Source
Cook, Gerards, Schrijver, Tardos, Sensitivity theorems in integer linear programming, Math. Programming 34 (1986), p. 259, Theorem 9 [sic; cited as Theorem 8 on p. 260]
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.