Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.7 — integrality of a TU polyhedron with integer bounds

Proved
PochetWolsey.Decomposition.tu_box_integral

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

decompositioninteger-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1polyhedra

Let A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n be totally unimodular, and let b∈Zmb\in\mathbb Z^mb∈Zm and l,h∈Znl,h\in\mathbb Z^nl,h∈Zn. If

P={x∈Rn:Ax≤b, l≤x≤h}P=\{x\in\mathbb R^n:Ax\le b,\ l\le x\le h\}P={x∈Rn:Ax≤b, l≤x≤h}

is nonempty, every extreme point of PPP has integer coordinates. Thus PPP 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.

Preamble
import Mathlib
Formal statement
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
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, DOI 10.1007/0-387-33477-7, p. 204 (PDF 218), Theorem 6.7; definition of integral polyhedron, p. 203
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let m,nm,nm,n be natural numbers and AAA a real m×nm\times nm×n matrix. Let b∈Zmb\in\mathbb{Z}^mb∈Zm and l,h∈Znl,h\in\mathbb{Z}^nl,h∈Zn be integer vectors, all used as real numbers. Assume AAA is totally unimodular: every k×kk\times kk×k submatrix formed from kkk distinct rows and kkk distinct columns, for every k≥0k\ge0k≥0, has determinant in {−1,0,1}\{-1,0,1\}{−1,0,1}. Define

P={x∈Rn:Ax≤b, l≤x≤h},P=\{x\in\mathbb{R}^n : Ax\le b,\ l\le x\le h\},P={x∈Rn:Ax≤b, l≤x≤h},

with componentwise inequalities.

The statement asserts the following. If PPP is nonempty, then every extreme point xxx of PPP has every coordinate xjx_jxj​ equal to an integer. Here an extreme point is a point x∈Px\in Px∈P such that whenever xxx lies in the open segment between two points x1,x2∈Px^1,x^2\in Px1,x2∈P, both x1=xx^1=xx1=x and x2=xx^2=xx2=x.

Degenerate cases:

  • Empty box. If lj>hjl_j>h_jlj​>hj​ for some jjj, then PPP is empty and the nonemptiness hypothesis fails. More generally, an empty PPP has no extreme points.
  • n=0n=0n=0. PPP is the single point R0\mathbb{R}^0R0 when every bi≥0b_i\ge0bi​≥0, and is empty otherwise. The integrality conclusion has no coordinates to check.
  • m=0m=0m=0. PPP is the integer-cornered box ∏j[lj,hj]\prod_j[l_j,h_j]∏j​[lj​,hj​].
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me