Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Remark in §3.3 — if X⊆[0,1]nX \subseteq [0,1]^nX⊆[0,1]n, every point of XXX is a vertex of conv(X)\mathrm{conv}(X)conv(X)

Proved
Lubbecke2005.Discretization.binary_points_are_vertices

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

column-generationinteger-programmingp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedra

Let DDD be a rational m×nm \times nm×n matrix and d\mathbf dd a rational mmm-vector, let P={x∈Rn∣Dx⩾d, x⩾0}P = \{\mathbf x \in \mathbb R^n \mid D\mathbf x \geqslant \mathbf d,\ \mathbf x \geqslant \mathbf 0\}P={x∈Rn∣Dx⩾d, x⩾0} and X=P∩ZnX = P \cap \mathbb Z^nX=P∩Zn. Suppose X⊆[0,1]nX \subseteq [0,1]^nX⊆[0,1]n, so that X⊆{0,1}nX \subseteq \{0,1\}^nX⊆{0,1}n. Then every point of XXX is a vertex of the convex hull of XXX:

X⊆ext⁡(conv⁡(X)).X \subseteq \operatorname{ext}\bigl(\operatorname{conv}(X)\bigr).X⊆ext(conv(X)).

In this case the discretization (24) and the convexification (23) of the integer program coincide: every integer point is itself one of the extreme points pq\mathbf p_qpq​, so it is the trivial convex combination of one vertex. This is why many set-partitioning and set-covering decompositions need no separate discretization.

Formalization Note "Vertices of conv(X)" is read as the extreme points of the convex hull (Set.extremePoints ℝ (convexHull ℝ X)); since XXX is finite here, conv(X) is a polytope, whose vertices and extreme points coincide. The statement assumes neither P≠∅P \neq \emptysetP=∅ nor anything about DDD beyond the setting of Theorem 1; the paper states the Remark for the XXX of Theorem 1.

Preamble
import Mathlib
import Definitions.Def_Lubbecke2005_Discretization_Polyhedron
Formal statement
namespace Lubbecke2005.Discretization

/-- **Lübbecke–Desrosiers 2005, Remark in §3.3 (p. 1012).** In the special case
`X ⊆ [0, 1]ⁿ`, where `X = P ∩ ℤⁿ` and `P = {𝐱 ∈ ℝⁿ | D𝐱 ⩾ 𝐝, 𝐱 ⩾ 𝟎}`, every point of `X`
is a vertex (extreme point) of `conv(X)`. -/
theorem binary_points_are_vertices {m n : ℕ} (D : Matrix (Fin m) (Fin n) ℚ)
    (d : Fin m → ℚ)
    (hX : ∀ x ∈ integerPoints D d, ∀ j, x j ∈ Set.Icc (0 : ℝ) 1) :
    ∀ x ∈ integerPoints D d,
      x ∈ Set.extremePoints ℝ (convexHull ℝ (integerPoints D d)) := by sorry

end Lubbecke2005.Discretization
Source
Lübbecke and Desrosiers, Selected Topics in Column Generation, Operations Research 53(6), 2005, p. 1012, Remark in §3.3 (second sentence)
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me