Theorem 9.3 — discrete constant-capacity lot-sizing hull
ProvedPochetWolsey.Capacities.discrete_hullLet , , and for . Write , and assume the discrete lot-sizing feasible set is nonempty.
Then the original binary covering set has the exact convex-hull description
Thus rounded prefix inequalities and the setup bounds describe the entire hull.
Formalization Note The left-hand set is written explicitly using and binary setups. The hull is the ordinary real convex hull, without a closure operation.
import Mathlib import Definitions.Def_PochetWolsey_Capacities_Model
namespace PochetWolsey.Capacities
/-- Theorem 9.3, with both sets expanded from their original constraints. -/
theorem discrete_hull {n : ℕ} (hn : 0 < n) (C : ℝ) (hC : 0 < C)
(d : Fin n → ℝ) (hd : ∀ t, 0 ≤ d t ∧ d t ≤ C)
(hfeas : ({y : Fin n → ℝ | (∀ u, y u = 0 ∨ y u = 1) ∧
∀ t, (∑ u ∈ Finset.Iic t, d u) ≤ C * ∑ u ∈ Finset.Iic t, y u} : Set _).Nonempty) :
convexHull ℝ {y : Fin n → ℝ | (∀ u, y u = 0 ∨ y u = 1) ∧
∀ t, (∑ u ∈ Finset.Iic t, d u) ≤ C * ∑ u ∈ Finset.Iic t, y u} =
{y : Fin n → ℝ | (∀ u, 0 ≤ y u ∧ y u ≤ 1) ∧
∀ t, (⌈(∑ u ∈ Finset.Iic t, d u) / C⌉ : ℤ) ≤
(∑ u ∈ Finset.Iic t, y u)} := by sorry
end PochetWolsey.Capacities
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The statement is parametrized by:
- with ; periods are in their usual order.
- with .
- with for every .
Write , and for write . Define
The hypothesis is that is nonempty.
Conclusion. The real convex hull of in equals
with each ceiling an integer compared as a real. This is a set equality, so it asserts both inclusions.
Degenerate cases.
- The nonemptiness hypothesis follows from the bounds , because the all-ones vector lies in . So the statement is not vacuous.
- The cases and are excluded.
- If all , every ceiling is and the right-hand side is the whole cube .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.