Theorem 6.7 — integrality of a TU polyhedron with integer bounds
ProvedPochetWolsey.Decomposition.tu_box_integralLet be totally unimodular, and let and . If
is nonempty, every extreme point of has integer coordinates. Thus is integral in the terminology of Section 6.4. This companion result supplies an integrality criterion for subsequent formulation arguments.
Formalization Note The coordinate bounds are arbitrary integers, including negative values. Nonemptiness is explicit; no nonnegativity restriction, integrality of arbitrary feasible points, or integrality conclusion is assumed.
import Mathlib
namespace PochetWolsey.Decomposition
theorem tu_box_integral {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℤ) (l h : Fin n → ℤ) (hA : A.IsTotallyUnimodular) :
let P : Set (Fin n → ℝ) := {x | (∀ i, (∑ j, A i j * x j) ≤ (b i : ℝ)) ∧
(∀ j, (l j : ℝ) ≤ x j) ∧ (∀ j, x j ≤ (h j : ℝ))}
P.Nonempty → ∀ x ∈ Set.extremePoints ℝ P, ∀ j, ∃ z : ℤ, x j = (z : ℝ) := by sorry
end PochetWolsey.Decomposition
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be natural numbers and a real matrix. Let and be integer vectors, all used as real numbers. Assume is totally unimodular: every submatrix formed from distinct rows and distinct columns, for every , has determinant in . Define
with componentwise inequalities.
The statement asserts the following. If is nonempty, then every extreme point of has every coordinate equal to an integer. Here an extreme point is a point such that whenever lies in the open segment between two points , both and .
Degenerate cases:
- Empty box. If for some , then is empty and the nonemptiness hypothesis fails. More generally, an empty has no extreme points.
- . is the single point when every , and is empty otherwise. The integrality conclusion has no coordinates to check.
- . is the integer-cornered box .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.