Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.5 — complete uncapacitated lot-sizing hull

Disproved
PochetWolsey.Reformulation.ls_u_hull

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

convex-hulllot-sizingp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planning

Let n≥1n\ge1n≥1 and dt≥0d_t\ge0dt​≥0. Fix M>0M>0M>0 with M≥∑tdtM\ge\sum_t d_tM≥∑t​dt​. Let PPP be the continuous relaxation defined by xt∈Rx_t\in\mathbb Rxt​∈R, st≥0s_t\ge0st​≥0, 0≤yt≤10\le y_t\le10≤yt​≤1, s0=sn=0s_0=s_n=0s0​=sn​=0, and

st−1+xt=dt+st,xt≤Myt.s_{t-1}+x_t=d_t+s_t,\qquad x_t\le My_t.st−1​+xt​=dt​+st​,xt​≤Myt​.

Let XXX be the subset with binary setups. Write djl=∑k=jldkd_{jl}=\sum_{k=j}^l d_kdjl​=∑k=jl​dk​. Then

conv⁡(X)={(x,s,y)∈P: ∑j∈Sxj≤∑j∈Sdjlyj+slfor all 1≤l≤n, S⊆{1,…,l}}.\operatorname{conv}(X)=\left\{(x,s,y)\in P:\ \sum_{j\in S}x_j\le\sum_{j\in S}d_{jl}y_j+s_l\quad\text{for all }1\le l\le n,\ S\subseteq\{1,\ldots,l\}\right\}.conv(X)=⎩⎨⎧​(x,s,y)∈P: j∈S∑​xj​≤j∈S∑​djl​yj​+sl​for all 1≤l≤n, S⊆{1,…,l}⎭⎬⎫​.

This is a complete description in the original production, stock, and setup variables, independent of any particular objective.

Formalization Note This is the faithful literal reading of the displayed domain (7.4), which prints x∈Rnx\in\mathbb R^nx∈Rn without a nonnegativity subscript, and defines XLS−UX^{LS-U}XLS−U by those constraints on p. 209. It is expected to be disproved: FINDINGS.yaml records the two-period counterexample and the companion corrected item restores x≥0x\ge0x≥0, as in (4.5) and (7.47). The claim is preserved rather than silently repaired. Fin n shifts production indices down by one; stocks retain their boundary indices. “Large” MMM means M>0M>0M>0 and M≥∑tdtM\ge\sum_t d_tM≥∑t​dt​.

Preamble
import Mathlib
Formal statement
namespace PochetWolsey.Reformulation

theorem ls_u_hull
    (n : ℕ) (hn : 0 < n) (d : Fin n → ℝ) (hd : ∀ t, 0 ≤ d t)
    (M : ℝ) (hM : 0 < M) (hlarge : (∑ t, d t) ≤ M) :
    let P : Set ((Fin n → ℝ) × (Fin (n + 1) → ℝ) × (Fin n → ℝ)) :=
      {z | z.2.1 0 = 0 ∧ z.2.1 (Fin.last n) = 0 ∧
        (∀ k, 0 ≤ z.2.1 k) ∧
        (∀ t, 0 ≤ z.2.2 t ∧ z.2.2 t ≤ 1 ∧
          z.2.1 t.castSucc + z.1 t = d t + z.2.1 t.succ ∧
          z.1 t ≤ M * z.2.2 t)}
    let X := {z | z ∈ P ∧ ∀ t, z.2.2 t = 0 ∨ z.2.2 t = 1}
    convexHull ℝ X =
      {z | z ∈ P ∧ ∀ (l : Fin n) (S : Finset (Fin n)),
        (∀ j ∈ S, j ≤ l) →
          (∑ j ∈ S, z.1 j) ≤
            (∑ j ∈ S, (∑ k ∈ Finset.Icc j l, d k) * z.2.2 j) + z.2.1 l.succ} := by sorry

end PochetWolsey.Reformulation
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 218 (PDF 232), Theorem 7.5 (compare Theorem 4.2, whose domain explicitly requires nonnegative production); DOI 10.1007/0-387-33477-7
Read-back

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

Data. Fix a natural number nnn with n>0n > 0n>0, a real vector ddd indexed by periods t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}, and a real number MMM. The hypotheses are dt≥0d_t \ge 0dt​≥0 for all ttt, M>0M > 0M>0, and ∑tdt≤M\sum_t d_t \le M∑t​dt​≤M.

Points. A point is a triple z=(x,s,y)z = (x, s, y)z=(x,s,y) in Rn×Rn+1×Rn\mathbb{R}^n \times \mathbb{R}^{n+1} \times \mathbb{R}^nRn×Rn+1×Rn, where sss is indexed by 0,…,n0,\dots,n0,…,n.

The set PPP. PPP consists of the zzz with

s0=0,sn=0,sk≥0 (k=0,…,n),s_0 = 0,\quad s_n = 0,\quad s_k \ge 0\ (k=0,\dots,n),s0​=0,sn​=0,sk​≥0 (k=0,…,n),

and, for every period ttt,

0≤yt≤1,st+xt=dt+st+1,xt≤M yt.0 \le y_t \le 1,\quad s_t + x_t = d_t + s_{t+1},\quad x_t \le M\,y_t .0≤yt​≤1,st​+xt​=dt​+st+1​,xt​≤Myt​.

There is no constraint xt≥0x_t \ge 0xt​≥0. XXX is the subset of PPP where every yt∈{0,1}y_t \in \{0,1\}yt​∈{0,1}.

Claim. The real convex hull of XXX, taken in the product space Rn×Rn+1×Rn\mathbb{R}^n \times \mathbb{R}^{n+1} \times \mathbb{R}^nRn×Rn+1×Rn, equals the set of points z=(x,s,y)∈Pz = (x,s,y) \in Pz=(x,s,y)∈P satisfying the following. For every period lll and every finite set SSS of periods all of whose elements are ≤l\le l≤l,

∑j∈Sxj  ≤  ∑j∈S(∑k=jldk)yj  +  sl+1.\sum_{j \in S} x_j \;\le\; \sum_{j\in S}\Big(\sum_{k=j}^{l} d_k\Big) y_j \;+\; s_{l+1}.j∈S∑​xj​≤j∈S∑​(k=j∑l​dk​)yj​+sl+1​.

This is an equality of sets: both inclusions are asserted.

Degenerate cases.

  • The choice S=∅S = \emptysetS=∅ contributes only 0≤sl+10 \le s_{l+1}0≤sl+1​, already implied by PPP.
  • For l=n−1l = n-1l=n−1, the term sl+1s_{l+1}sl+1​ equals sn=0s_n = 0sn​=0.
  • For n=1n = 1n=1, PPP forces s0=s1=0s_0 = s_1 = 0s0​=s1​=0 and x0=d0x_0 = d_0x0​=d0​. Then XXX consists of the points with y0∈{0,1}y_0 \in \{0,1\}y0​∈{0,1} and d0≤My0d_0 \le M y_0d0​≤My0​.
  • If all dt=0d_t = 0dt​=0, xxx is not forced to vanish, since negative xtx_txt​ is not excluded by PPP. The claim is still asserted.
  • Because xxx may be negative in both PPP and XXX, the equality is asserted for these sets as written.
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