Remark in §3.3 — if , every point of is a vertex of
ProvedLubbecke2005.Discretization.binary_points_are_verticesLet be a rational matrix and a rational -vector, let and . Suppose , so that . Then every point of is a vertex of the convex hull of :
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 , 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 is finite here, conv(X) is a polytope, whose vertices and extreme points coincide. The statement assumes neither nor anything about beyond the setting of Theorem 1; the paper states the Remark for the of Theorem 1.
import Mathlib import Definitions.Def_Lubbecke2005_Discretization_Polyhedron
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.