Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.4 — validity of the (l,S)(l,S)(l,S) inequalities

Disproved
PochetWolsey.Reformulation.ls_inequality_valid

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, dt≥0d_t\ge0dt​≥0, and let (x,s,y)(x,s,y)(x,s,y) be a feasible uncapacitated lot-sizing plan: production is real-valued and stock is nonnegative, initial and final stocks are zero, setups are binary, st−1+xt=dt+sts_{t-1}+x_t=d_t+s_tst−1​+xt​=dt​+st​, and xt≤Mytx_t\le My_txt​≤Myt​ for a positive M≥∑tdtM\ge\sum_t d_tM≥∑t​dt​. For 1≤l≤n1\le l\le n1≤l≤n, put L={1,…,l}L=\{1,\ldots,l\}L={1,…,l} and take any S⊆LS\subseteq LS⊆L. With djl=∑k=jldkd_{jl}=\sum_{k=j}^l d_kdjl​=∑k=jl​dk​, the inequality

∑j∈Sxj≤∑j∈Sdjlyj+sl\sum_{j\in S}x_j\le\sum_{j\in S}d_{jl}y_j+s_lj∈S∑​xj​≤j∈S∑​djl​yj​+sl​

is valid for every such plan. These inequalities constrain the interaction between production and setup decisions over each prefix of the horizon.

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_inequality_valid
    (n : ℕ) (hn : 0 < n) (d x y : Fin n → ℝ) (s : Fin (n + 1) → ℝ)
    (hd : ∀ t, 0 ≤ d t) (hs : ∀ k, 0 ≤ s k)
    (hstart : s 0 = 0) (hend : s (Fin.last n) = 0)
    (hy : ∀ t, y t = 0 ∨ y t = 1)
    (hbalance : ∀ t, s t.castSucc + x t = d t + s t.succ)
    (M : ℝ) (hM : 0 < M) (hlarge : (∑ t, d t) ≤ M)
    (hsetup : ∀ t, x t ≤ M * y t)
    (l : Fin n) (S : Finset (Fin n)) (hS : ∀ j ∈ S, j ≤ l) :
    (∑ j ∈ S, x j) ≤
      (∑ j ∈ S, (∑ k ∈ Finset.Icc j l, d k) * y j) + s l.succ := by sorry

end PochetWolsey.Reformulation
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 218 (PDF 232), Proposition 7.4, Eq. (7.10); 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. Periods are t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}. The data are:

  • real vectors d,x,yd, x, yd,x,y indexed by periods;
  • a real vector sss indexed by k∈{0,…,n}k \in \{0,\dots,n\}k∈{0,…,n};
  • a real number MMM;
  • a period lll;
  • a finite set SSS of periods.

Hypotheses.

  • dt≥0d_t \ge 0dt​≥0 for all ttt;
  • sk≥0s_k \ge 0sk​≥0 for all kkk;
  • s0=0s_0 = 0s0​=0 and sn=0s_n = 0sn​=0;
  • each yty_tyt​ is 000 or 111;
  • st+xt=dt+st+1s_t + x_t = d_t + s_{t+1}st​+xt​=dt​+st+1​ for every period ttt;
  • M>0M > 0M>0 and ∑t=0n−1dt≤M\sum_{t=0}^{n-1} d_t \le M∑t=0n−1​dt​≤M;
  • xt≤M ytx_t \le M\, y_txt​≤Myt​ for every ttt;
  • every j∈Sj \in Sj∈S satisfies j≤lj \le lj≤l.

There is no hypothesis that xt≥0x_t \ge 0xt​≥0.

Claim.

∑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​,

where the inner sum runs over periods kkk with j≤k≤lj \le k \le lj≤k≤l. Since j≤lj \le lj≤l, that range is never empty.

Degenerate cases.

  • If S=∅S = \emptysetS=∅, the claim reads 0≤sl+10 \le s_{l+1}0≤sl+1​, which is among the hypotheses.
  • If l=n−1l = n-1l=n−1, then sl+1=sn=0s_{l+1} = s_n = 0sl+1​=sn​=0 and the right side is just the weighted demand sum.
  • Because xxx may take negative values, the claim is asserted for such xxx as well.
  • The hypotheses are jointly satisfiable. For example, take x0=∑tdtx_0 = \sum_t d_tx0​=∑t​dt​, y0=1y_0 = 1y0​=1, xt=yt=0x_t = y_t = 0xt​=yt​=0 for t≥1t \ge 1t≥1, and stocks determined by the balance equations.
  • The case n=1n = 1n=1 forces l=0l = 0l=0, s0=s1=0s_0 = s_1 = 0s0​=s1​=0 and x0=d0x_0 = d_0x0​=d0​.
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