Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.15 — printed Wagner–Whitin start-up hull

Disproved
PochetWolsey.BacklogStartup.ww_startup_hull

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

backlogginglot-sizingp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planningstart-up-costs

Let n≥1n\ge1n≥1 and dt≥0d_t\ge0dt​≥0. Let XWW−U−SCX^{WW-U-SC}XWW−U−SC be the set defined by (10.14)–(10.17), with given y0∈{0,1}y_0\in\{0,1\}y0​∈{0,1}. The printed theorem asserts

conv⁡(XWW−U−SC)=Pprinted,\operatorname{conv}(X^{WW-U-SC})=P_{\rm printed},conv(XWW−U−SC)=Pprinted​,

where PprintedP_{\rm printed}Pprinted​ is the system (10.11), (10.15), (10.16), s≥0s\ge0s≥0, and 0≤y≤10\le y\le10≤y≤1. This asserts equality of the entire sets in (s,y,z)(s,y,z)(s,y,z) space, including the free nonnegative terminal-stock direction.

The item preserves the printed hull assertion as the source milestone. Finding F1 supplies a counterexample to its missing lower bound on start-ups, so this faithful item is expected to be disproved.

Formalization Note The right-hand side deliberately does not impose z≥0z\ge0z≥0. The corrected variant is separate; it does not replace this statement or its milestone.

Initial-state convention: the parameter y0 is the same fixed binary datum in every feasible set in this item (printed p. 138 / PDF 155); it is not optimized.

Preamble
import Mathlib
import Definitions.Def_PochetWolsey_BacklogStartup_StartupModel
Formal statement
namespace PochetWolsey.BacklogStartup

theorem ww_startup_hull {n : ℕ} (y0 : ℝ) (hy0 : y0 = 0 ∨ y0 = 1) (hn : 0 < n) (d : Fin n → ℝ)
    (hd : ∀ t, 0 ≤ d t) :
    convexHull ℝ (WWStartup y0 d) = PrintedStartupHull y0 d := by sorry

end PochetWolsey.BacklogStartup
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 323 (PDF 336), Theorem 10.15
Read-back

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

Setting. Let:

  • n≥1n \ge 1n≥1;
  • y0∈{0,1}y^0 \in \{0,1\}y0∈{0,1};
  • d∈Rnd \in \mathbb{R}^nd∈Rn with every dt≥0d_t \ge 0dt​≥0.

Points are p=(s,y,z)∈Rn+1×Rn×Rnp = (s, y, z) \in \mathbb{R}^{n+1} \times \mathbb{R}^n \times \mathbb{R}^np=(s,y,z)∈Rn+1×Rn×Rn, where sss has coordinates s0,…,sns_0,\dots,s_ns0​,…,sn​ and yyy, zzz have coordinates 1..n1..n1..n. Write:

  • vˉt=vt\bar v_t = v_tvˉt​=vt​ for 1≤t≤n1 \le t \le n1≤t≤n, and 000 otherwise;
  • y^0=y0\hat y_0 = y^0y^​0​=y0 and y^t=yˉt\hat y_t = \bar y_ty^​t​=yˉ​t​ for t≥1t \ge 1t≥1;
  • Dkl=∑t=kldˉtD_{kl} = \sum_{t=k}^{l} \bar d_tDkl​=∑t=kl​dˉt​.

The set WWW. WWW is the set of points with:

  • s≥0s \ge 0s≥0;
  • every yty_tyt​ and every ztz_tzt​ in {0,1}\{0,1\}{0,1};
  • for every t∈{1,…,n}t \in \{1,\dots,n\}t∈{1,…,n}:
yt−y^t−1≤zt≤yt;y_t - \hat y_{t-1} \le z_t \le y_t;yt​−y^​t−1​≤zt​≤yt​;
  • for all 1≤k≤l≤n1 \le k \le l \le n1≤k≤l≤n:
Dkl≤sk−1+∑u=klDul yu.D_{kl} \le s_{k-1} + \sum_{u=k}^{l} D_{ul}\, y_u.Dkl​≤sk−1​+u=k∑l​Dul​yu​.

The set PPP. PPP is the set of points with:

  • s≥0s \ge 0s≥0;
  • every yt∈[0,1]y_t \in [0,1]yt​∈[0,1], and no further condition on zzz;
  • for every t∈{1,…,n}t \in \{1,\dots,n\}t∈{1,…,n}:
yt−y^t−1≤zt≤yt;y_t - \hat y_{t-1} \le z_t \le y_t;yt​−y^​t−1​≤zt​≤yt​;
  • for all 1≤k≤l≤n1 \le k \le l \le n1≤k≤l≤n:
∑u=kldu(1−yk−∑j=k+1uzj)≤sk−1.\sum_{u=k}^{l} d_u\Bigl(1 - y_k - \sum_{j=k+1}^{u} z_j\Bigr) \le s_{k-1}.u=k∑l​du​(1−yk​−j=k+1∑u​zj​)≤sk−1​.

Claim. The convex hull (the set of all finite convex combinations, with no closure taken) of WWW, in the real vector space Rn+1×Rn×Rn\mathbb{R}^{n+1} \times \mathbb{R}^n \times \mathbb{R}^nRn+1×Rn×Rn, equals PPP exactly.

Degenerate cases.

  • n=0n = 0n=0 is excluded.
  • Both sets are unbounded in sss, since sss has no upper bound.
  • In PPP, coordinates ztz_tzt​ may be negative. The lower bound yt−y^t−1y_t - \hat y_{t-1}yt​−y^​t−1​ can be as low as −1-1−1, so the claim asserts that every such point of PPP is a convex combination of points of WWW, whose zzz-coordinates are all 000 or 111.
  • If d=0d = 0d=0, every demand constraint in both sets reduces to sk−1≥0s_{k-1} \ge 0sk−1​≥0.
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