Proposition 13.5 — nested optimal assembly plan (literal ML-A claim)
DisprovedPochetWolsey.Assembly.assembly_nestedConsider 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 ; stock boundary precedes period . Production, physical holding, and setup costs are real numbers. Write . Assume, for every item and adjacent pair of periods,
The asserted conclusion is
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 is the book’s item . 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.
import Definitions.Def_PochetWolsey_Assembly_Model
/- 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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix natural numbers and with and . Items are indexed by , so there are at least two. Production periods are indexed by , so there is at least one. Stock levels are indexed by time points .
The model. Let be any model, consisting of:
- a successor map with and for every . This makes the items a tree rooted at item , in which each item feeds into .
- a demand for each period .
- real production costs , for items and periods .
- real holding costs , for items and time points .
- real setup costs , for items and periods .
No sign condition is imposed on , or ; any of them may be negative.
Capacities. Let be either "no capacity" or a capacity table , which assigns a nonnegative real to each item and period .
Plans. A plan consists of:
- real production quantities , for periods ;
- real stocks , for time points ;
- Boolean setup flags , written as an indicator.
The effective demand of item in period is if , and otherwise. That is, one unit of is consumed per unit of its successor produced, in the same period.
Feasibility. A plan is feasible for when all of the following hold:
- and for all and ;
- and for every item ;
- the balance equation holds for every and every period :
- implies ;
- if is a capacity table , then for all and . If is "no capacity", this condition is absent.
Cost. The cost of a plan is
A plan is optimal if it is feasible and its cost is the cost of every feasible plan. Nothing ties to whether : a setup may be switched on with zero production, and its setup cost is still paid.
Hypotheses. The theorem assumes three things.
- At least one feasible plan exists for .
- The Wagner–Whitin condition holds. Define the echelon holding cost
which is the holding cost of minus the holding costs of its direct predecessors . The condition requires, for every item and every pair of consecutive periods :
- Setup costs are nonincreasing in time: for every item and every pair of consecutive periods .
Conclusion. There exists a plan that is optimal for and is nested. Nested means that for every item and every period :
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 . The conclusion is pure existence: it does not say that every optimal plan is nested.
Degenerate cases.
- One period (). There is no pair of consecutive periods, so the Wagner–Whitin and nonincreasing-setup hypotheses are vacuously true. Feasibility forces , hence .
- Two items (). Necessarily .
- Leaf items. For an item with no predecessors, the sum in is empty, so . The root never counts as its own predecessor, because is excluded.
- Unused holding costs. The values and never enter the Wagner–Whitin condition. In the cost they multiply stocks that feasibility forces to be .
- Zero demand. If all demands are , the all-zero production and stock plan satisfies the balance equations.
- Zero capacity. Capacities may be , which forces the corresponding .
- Satisfiability of the feasibility hypothesis. When is "no capacity", the hypothesis is always satisfiable: produce with all stocks and all setups true. When 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.