Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.1 — zero-inventory optimal production plan

Disproved
PochetWolsey.Reformulation.zero_inventory_optimal

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

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

Consider a finite horizon of n≥1n\ge1n≥1 periods, nonnegative demands dtd_tdt​, arbitrary real unit production costs ptp_tpt​, stock costs hth_tht​, and setup costs qtq_tqt​. Let M>0M>0M>0 satisfy M≥∑tdtM\ge\sum_t d_tM≥∑t​dt​. The feasible set XXX consists of real production xtx_txt​ and nonnegative stocks sts_tst​, binary setups yty_tyt​, zero initial and final stocks, 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​.

There is a feasible plan minimizing ∑tptxt+∑t=0nhtst+∑tqtyt\sum_t p_tx_t+\sum_{t=0}^n h_ts_t+\sum_t q_ty_t∑t​pt​xt​+∑t=0n​ht​st​+∑t​qt​yt​ over all of XXX such that

st−1xt=0(t=1,…,n).s_{t-1}x_t=0\qquad(t=1,\ldots,n).st−1​xt​=0(t=1,…,n).

Thus at least one optimal plan produces only when its entering inventory is zero. Setups without production remain permitted, including when setup costs are negative.

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 zero_inventory_optimal
    (n : ℕ) (hn : 0 < n) (d p q : Fin n → ℝ) (h : Fin (n + 1) → ℝ)
    (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}
    let cost := fun z : (Fin n → ℝ) × (Fin (n + 1) → ℝ) × (Fin n → ℝ) =>
      (∑ t, p t * z.1 t) + (∑ k, h k * z.2.1 k) + (∑ t, q t * z.2.2 t)
    ∃ z ∈ X, (∀ z' ∈ X, cost z ≤ cost z') ∧
      ∀ t, z.2.1 t.castSucc * z.1 t = 0 := by sorry

end PochetWolsey.Reformulation
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 210 (PDF 224), Proposition 7.1; model (7.1)–(7.6); 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 indexed by t∈{0,…,n−1}t \in \{0, \dots, n-1\}t∈{0,…,n−1}, and "stock" positions are indexed by k∈{0,…,n}k \in \{0, \dots, n\}k∈{0,…,n}. The data are:

  • real vectors d=(dt)d = (d_t)d=(dt​), p=(pt)p = (p_t)p=(pt​), q=(qt)q = (q_t)q=(qt​) indexed by periods;
  • a real vector h=(hk)h = (h_k)h=(hk​) indexed by k∈{0,…,n}k \in \{0,\dots,n\}k∈{0,…,n};
  • a real number MMM.

The hypotheses are:

  • dt≥0d_t \ge 0dt​≥0 for every ttt;
  • M>0M > 0M>0;
  • ∑t=0n−1dt≤M\sum_{t=0}^{n-1} d_t \le M∑t=0n−1​dt​≤M.

No sign condition is placed on ppp, qqq or hhh.

Points. A point is a triple z=(x,s,y)z = (x, s, y)z=(x,s,y) with x∈Rnx \in \mathbb{R}^nx∈Rn (indexed by periods), s∈Rn+1s \in \mathbb{R}^{n+1}s∈Rn+1 (indexed by 0,…,n0,\dots,n0,…,n) and y∈Rny \in \mathbb{R}^ny∈Rn (indexed by periods).

The set PPP. PPP is the set of all such zzz with

s0=0,sn=0,sk≥0  (k=0,…,n),s_0 = 0,\qquad s_n = 0,\qquad 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,\qquad s_t + x_t = d_t + s_{t+1},\qquad 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; the entries of xxx may be negative as long as the constraints above hold. XXX is the subset of PPP in which every yty_tyt​ equals 000 or 111.

Cost. The cost of a point is

c(z)=∑t=0n−1ptxt+∑k=0nhksk+∑t=0n−1qtyt.c(z) = \sum_{t=0}^{n-1} p_t x_t + \sum_{k=0}^{n} h_k s_k + \sum_{t=0}^{n-1} q_t y_t .c(z)=t=0∑n−1​pt​xt​+k=0∑n​hk​sk​+t=0∑n−1​qt​yt​.

Claim. There exists a point z∗=(x∗,s∗,y∗)∈Xz^\ast = (x^\ast, s^\ast, y^\ast) \in Xz∗=(x∗,s∗,y∗)∈X with both of the following properties:

  • c(z∗)≤c(z′)c(z^\ast) \le c(z')c(z∗)≤c(z′) for every z′∈Xz' \in Xz′∈X, so z∗z^\astz∗ minimises ccc over XXX;
  • st∗ xt∗=0s^\ast_t \, x^\ast_t = 0st∗​xt∗​=0 for every period t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}. Here st∗s^\ast_tst∗​ is the stock entry at the same index ttt, the start of period ttt.

The claim asserts the existence of some minimiser with this product property. It does not assert that every minimiser has it.

Degenerate cases.

  • The hypotheses involve only the data and are satisfiable.
  • The smallest allowed case is n=1n = 1n=1. Then s0=s1=0s_0 = s_1 = 0s0​=s1​=0, so x0=d0x_0 = d_0x0​=d0​, and the product condition is automatic.
  • At t=0t = 0t=0 the product condition always holds, because s0=0s_0 = 0s0​=0.
  • The terms h0s0h_0 s_0h0​s0​ and hnsnh_n s_nhn​sn​ in the cost are always 000 on PPP.
  • Because ppp, qqq, hhh may be negative or zero, the claim is asserted for arbitrary real cost coefficients.
  • Because xxx is not required to be nonnegative, the minimisation ranges over points with possibly negative xtx_txt​.
  • The hypotheses d≥0d \ge 0d≥0, M>0M > 0M>0 and ∑tdt≤M\sum_t d_t \le M∑t​dt​≤M constrain the data only. They are not repeated inside PPP, except that MMM appears in xt≤Mytx_t \le M y_txt​≤Myt​.
  • If all dt=0d_t = 0dt​=0, the hypotheses remain satisfiable.
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