Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 13.5 — nested optimal assembly plan (literal ML-A claim)

Disproved
PochetWolsey.Assembly.assembly_nested

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

assembly-systemslot-sizingp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planning

Consider a feasible assembly lot-sizing system with at least two items, a positive finite horizon, unit utilization factors, zero lead times, a unique end-product with nonnegative external demand, and zero endpoint stocks. Production periods are numbered 0,…,n−10,\ldots,n-10,…,n−1; stock boundary ttt precedes period ttt. Production, physical holding, and setup costs are real numbers. Write Hti=hti−∑j:D(j)=ihtjH^i_t=h^i_t-\sum_{j:D(j)=i}h^j_tHti​=hti​−∑j:D(j)=i​htj​. Assume, for every item and adjacent pair of periods,

pti+Ht+1i−pt+1i≥0,qti≥qt+1i.p^i_t+H^i_{t+1}-p^i_{t+1}\ge0,\qquad q^i_t\ge q^i_{t+1}.pti​+Ht+1i​−pt+1i​≥0,qti​≥qt+1i​.

The asserted conclusion is

∃ an optimal plan (x,s,y):xti>0⟹xtD(i)>0(i intermediate).\exists\text{ an optimal plan }(x,s,y):\quad x^i_t>0\Longrightarrow x^{D(i)}_t>0\quad(i\text{ intermediate}).∃ an optimal plan (x,s,y):xti​>0⟹xtD(i)​>0(i intermediate).

The printed ML-A qualifier is retained: capacities may be absent or may be finite nonnegative item-period bounds. The statement is the source anchor; its capacitated reading is contradicted by finding F1.

Formalization Note Nonemptiness of the feasible set makes explicit the implicit meaning of an optimization problem admitting a solution; it does not assume optimality or nesting. Zero-based item 000 is the book’s item 111. No nonnegative-setup-cost condition is added: that condition appears only in the subsequent recursion. The missing uncapacitated qualifier is deliberately not repaired in this item.

Preamble
import Definitions.Def_PochetWolsey_Assembly_Model
Formal statement
/- Imported definition bodies, reproduced verbatim for standalone inspection.
import Mathlib

open scoped BigOperators

namespace PochetWolsey.Assembly

structure Model (m n : ℕ) where
  successor : Fin (m + 1) → Fin (m + 1)
  root_successor : successor 0 = 0
  successor_lt : ∀ i, i ≠ 0 → (successor i).val < i.val
  demand : Fin n → ℝ
  demand_nonneg : ∀ t, 0 ≤ demand t
  productionCost : Fin (m + 1) → Fin n → ℝ
  holdingCost : Fin (m + 1) → Fin (n + 1) → ℝ
  setupCost : Fin (m + 1) → Fin n → ℝ

structure Plan (m n : ℕ) where
  production : Fin (m + 1) → Fin n → ℝ
  stock : Fin (m + 1) → Fin (n + 1) → ℝ
  setup : Fin (m + 1) → Fin n → Bool

def Capacity (m n : ℕ) := Fin (m + 1) → Fin n → NNReal

def IsSeries {m n : ℕ} (I : Model m n) : Prop :=
  ∀ i, i ≠ 0 → (I.successor i).val + 1 = i.val

noncomputable def effectiveDemand {m n : ℕ} (I : Model m n) (a : Plan m n)
    (i : Fin (m + 1)) (t : Fin n) : ℝ :=
  if i = 0 then I.demand t else a.production (I.successor i) t

def Feasible {m n : ℕ} (I : Model m n) (c : Option (Capacity m n))
    (a : Plan m n) : Prop :=
  (∀ i t, 0 ≤ a.production i t) ∧
  (∀ i t, 0 ≤ a.stock i t) ∧
  (∀ i, a.stock i 0 = 0 ∧ a.stock i (Fin.last n) = 0) ∧
  (∀ i t, a.stock i t.castSucc + a.production i t =
    effectiveDemand I a i t + a.stock i t.succ) ∧
  (∀ i t, a.setup i t = false → a.production i t = 0) ∧
  (∀ C, c = some C → ∀ i t,
    a.production i t ≤ (C i t : ℝ) * (if a.setup i t then 1 else 0))

noncomputable def cost {m n : ℕ} (I : Model m n) (a : Plan m n) : ℝ :=
  (∑ i, ∑ t, I.productionCost i t * a.production i t) +
  (∑ i, ∑ t, I.holdingCost i t * a.stock i t) +
  (∑ i, ∑ t, I.setupCost i t * (if a.setup i t then 1 else 0))

def Optimal {m n : ℕ} (I : Model m n) (c : Option (Capacity m n))
    (a : Plan m n) : Prop :=
  Feasible I c a ∧ ∀ b, Feasible I c b → cost I a ≤ cost I b

def Nested {m n : ℕ} (I : Model m n) (a : Plan m n) : Prop :=
  ∀ i t, i ≠ 0 → 0 < a.production i t → 0 < a.production (I.successor i) t

def ZeroStock {m n : ℕ} (a : Plan m n) : Prop :=
  ∀ i t, a.stock i t.castSucc * a.production i t = 0

noncomputable def echelonHolding {m n : ℕ} (I : Model m n)
    (i : Fin (m + 1)) (t : Fin (n + 1)) : ℝ :=
  I.holdingCost i t -
    ∑ j ∈ Finset.univ.filter (fun j => j ≠ 0 ∧ I.successor j = i), I.holdingCost j t

def WagnerWhitin {m n : ℕ} (I : Model m n) : Prop :=
  ∀ i (t u : Fin n), u.val = t.val + 1 →
    0 ≤ I.productionCost i t + echelonHolding I i t.succ - I.productionCost i u

def NonincreasingSetups {m n : ℕ} (I : Model m n) : Prop :=
  ∀ i (t u : Fin n), u.val = t.val + 1 → I.setupCost i u ≤ I.setupCost i t

def StationaryCosts {m n : ℕ} (I : Model m n) : Prop :=
  (∀ i (t u : Fin n), I.productionCost i t = I.productionCost i u) ∧
  (∀ i (t u : Fin (n + 1)), I.holdingCost i t = I.holdingCost i u) ∧
  (∀ i (t u : Fin n), I.setupCost i t = I.setupCost i u)

noncomputable def demandInterval {n : ℕ} (d : Fin n → ℝ) (α β : Fin n) : ℝ :=
  ∑ t ∈ Finset.univ.filter (fun t => α ≤ t ∧ t ≤ β), d t

def DependentBatches {m n : ℕ} (I : Model m n) (a : Plan m n) : Prop :=
  ∀ i t, 0 < a.production i t → ∃ α β : Fin n,
    t ≤ α ∧ α ≤ β ∧ a.production i t = demandInterval (effectiveDemand I a i) α β

def FinalDemandBatches {m n : ℕ} (I : Model m n) (a : Plan m n) : Prop :=
  ∀ i t, 0 < a.production i t → ∃ α β : Fin n,
    t ≤ α ∧ α ≤ β ∧ a.production i t = demandInterval I.demand α β

end PochetWolsey.Assembly
-/

namespace PochetWolsey.Assembly

theorem assembly_nested {m n : ℕ} (hm : 0 < m) (hn : 0 < n)
    (I : Model m n) (c : Option (Capacity m n))
    (hfeasible : ∃ a : Plan m n, Feasible I c a)
    (hww : WagnerWhitin I) (hsetup : NonincreasingSetups I) :
    ∃ a : Plan m n, Optimal I c a ∧ Nested I a := by sorry

end PochetWolsey.Assembly
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, DOI 10.1007/0-387-33477-7, p. 407 (PDF 417), Proposition 13.5; original capacitated assembly model p. 406 (PDF 416)
Read-back

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

Fix natural numbers mmm and nnn with m>0m > 0m>0 and n>0n > 0n>0. Items are indexed by i∈{0,1,…,m}i \in \{0, 1, \dots, m\}i∈{0,1,…,m}, so there are at least two. Production periods are indexed by t∈{0,…,n−1}t \in \{0, \dots, n-1\}t∈{0,…,n−1}, so there is at least one. Stock levels are indexed by time points t∈{0,…,n}t \in \{0, \dots, n\}t∈{0,…,n}.

The model. Let III be any model, consisting of:

  • a successor map σ:{0,…,m}→{0,…,m}\sigma : \{0,\dots,m\} \to \{0,\dots,m\}σ:{0,…,m}→{0,…,m} with σ(0)=0\sigma(0) = 0σ(0)=0 and σ(i)<i\sigma(i) < iσ(i)<i for every i≠0i \neq 0i=0. This makes the items a tree rooted at item 000, in which each item i≠0i \neq 0i=0 feeds into σ(i)\sigma(i)σ(i).
  • a demand dt≥0d_t \ge 0dt​≥0 for each period ttt.
  • real production costs pi,tp_{i,t}pi,t​, for items iii and periods t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}.
  • real holding costs hi,th_{i,t}hi,t​, for items iii and time points t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n}.
  • real setup costs fi,tf_{i,t}fi,t​, for items iii and periods t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}.

No sign condition is imposed on ppp, hhh or fff; any of them may be negative.

Capacities. Let ccc be either "no capacity" or a capacity table CCC, which assigns a nonnegative real Ci,t≥0C_{i,t} \ge 0Ci,t​≥0 to each item iii and period ttt.

Plans. A plan aaa consists of:

  • real production quantities xi,tx_{i,t}xi,t​, for periods t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1};
  • real stocks si,ts_{i,t}si,t​, for time points t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n};
  • Boolean setup flags yi,t∈{true,false}y_{i,t} \in \{\text{true}, \text{false}\}yi,t​∈{true,false}, written [yi,t]∈{0,1}[y_{i,t}] \in \{0,1\}[yi,t​]∈{0,1} as an indicator.

The effective demand of item iii in period ttt is Di,t=dtD_{i,t} = d_tDi,t​=dt​ if i=0i = 0i=0, and Di,t=xσ(i),tD_{i,t} = x_{\sigma(i),t}Di,t​=xσ(i),t​ otherwise. That is, one unit of iii is consumed per unit of its successor produced, in the same period.

Feasibility. A plan is feasible for (I,c)(I, c)(I,c) when all of the following hold:

  • xi,t≥0x_{i,t} \ge 0xi,t​≥0 and si,t≥0s_{i,t} \ge 0si,t​≥0 for all iii and ttt;
  • si,0=0s_{i,0} = 0si,0​=0 and si,n=0s_{i,n} = 0si,n​=0 for every item iii;
  • the balance equation holds for every iii and every period ttt:
si,t+xi,t=Di,t+si,t+1;s_{i,t} + x_{i,t} = D_{i,t} + s_{i,t+1};si,t​+xi,t​=Di,t​+si,t+1​;
  • yi,t=falsey_{i,t} = \text{false}yi,t​=false implies xi,t=0x_{i,t} = 0xi,t​=0;
  • if ccc is a capacity table CCC, then xi,t≤Ci,t [yi,t]x_{i,t} \le C_{i,t}\,[y_{i,t}]xi,t​≤Ci,t​[yi,t​] for all iii and ttt. If ccc is "no capacity", this condition is absent.

Cost. The cost of a plan is

cost⁡(a)=∑i=0m∑t=0n−1pi,t xi,t  +  ∑i=0m∑t=0nhi,t si,t  +  ∑i=0m∑t=0n−1fi,t [yi,t].\operatorname{cost}(a) = \sum_{i=0}^{m}\sum_{t=0}^{n-1} p_{i,t}\,x_{i,t} \;+\; \sum_{i=0}^{m}\sum_{t=0}^{n} h_{i,t}\,s_{i,t} \;+\; \sum_{i=0}^{m}\sum_{t=0}^{n-1} f_{i,t}\,[y_{i,t}].cost(a)=i=0∑m​t=0∑n−1​pi,t​xi,t​+i=0∑m​t=0∑n​hi,t​si,t​+i=0∑m​t=0∑n−1​fi,t​[yi,t​].

A plan is optimal if it is feasible and its cost is ≤\le≤ the cost of every feasible plan. Nothing ties yi,ty_{i,t}yi,t​ to whether xi,t>0x_{i,t} > 0xi,t​>0: a setup may be switched on with zero production, and its setup cost is still paid.

Hypotheses. The theorem assumes three things.

  1. At least one feasible plan exists for (I,c)(I, c)(I,c).
  2. The Wagner–Whitin condition holds. Define the echelon holding cost
ei,t=hi,t−∑j≠0, σ(j)=ihj,t,e_{i,t} = h_{i,t} - \sum_{\substack{j \neq 0,\ \sigma(j) = i}} h_{j,t},ei,t​=hi,t​−j=0, σ(j)=i​∑​hj,t​,

which is the holding cost of iii minus the holding costs of its direct predecessors j≠0j \neq 0j=0. The condition requires, for every item iii and every pair of consecutive periods t,t+1∈{0,…,n−1}t, t+1 \in \{0,\dots,n-1\}t,t+1∈{0,…,n−1}:

pi,t+ei,t+1−pi,t+1≥0.p_{i,t} + e_{i,t+1} - p_{i,t+1} \ge 0.pi,t​+ei,t+1​−pi,t+1​≥0.
  1. Setup costs are nonincreasing in time: fi,t+1≤fi,tf_{i,t+1} \le f_{i,t}fi,t+1​≤fi,t​ for every item iii and every pair of consecutive periods t,t+1∈{0,…,n−1}t, t+1 \in \{0,\dots,n-1\}t,t+1∈{0,…,n−1}.

Conclusion. There exists a plan aaa that is optimal for (I,c)(I, c)(I,c) and is nested. Nested means that for every item i≠0i \neq 0i=0 and every period ttt:

xi,t>0  ⟹  xσ(i),t>0.x_{i,t} > 0 \implies x_{\sigma(i),t} > 0.xi,t​>0⟹xσ(i),t​>0.

In words, whenever a non-root item is produced in a period, its successor is also produced in that same period. The nesting condition places no constraint on the root item 000. The conclusion is pure existence: it does not say that every optimal plan is nested.

Degenerate cases.

  • One period (n=1n = 1n=1). There is no pair of consecutive periods, so the Wagner–Whitin and nonincreasing-setup hypotheses are vacuously true. Feasibility forces si,0=si,1=0s_{i,0} = s_{i,1} = 0si,0​=si,1​=0, hence xi,0=Di,0x_{i,0} = D_{i,0}xi,0​=Di,0​.
  • Two items (m=1m = 1m=1). Necessarily σ(1)=0\sigma(1) = 0σ(1)=0.
  • Leaf items. For an item with no predecessors, the sum in ei,te_{i,t}ei,t​ is empty, so ei,t=hi,te_{i,t} = h_{i,t}ei,t​=hi,t​. The root never counts as its own predecessor, because j=0j = 0j=0 is excluded.
  • Unused holding costs. The values hi,0h_{i,0}hi,0​ and hi,nh_{i,n}hi,n​ never enter the Wagner–Whitin condition. In the cost they multiply stocks that feasibility forces to be 000.
  • Zero demand. If all demands are 000, the all-zero production and stock plan satisfies the balance equations.
  • Zero capacity. Capacities may be 000, which forces the corresponding xi,t=0x_{i,t} = 0xi,t​=0.
  • Satisfiability of the feasibility hypothesis. When ccc is "no capacity", the hypothesis is always satisfiable: produce xi,t=Di,tx_{i,t} = D_{i,t}xi,t​=Di,t​ with all stocks 000 and all setups true. When ccc is a capacity table, the hypothesis is a genuine restriction.
  • Total functions and junk values. No division, natural-number subtraction, integral or supremum appears, so no junk values from Lean's total functions arise.
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