Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.12 — the printed combined formulation solves LS-U-B, SL, CP

Disproved
PochetWolsey.Variants.combined_formulation_solves

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

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

For the finite uncapacitated lot-sizing model with nonnegative fixed demands, KKK ordered production cost segments, LLL markets with nonnegative upper bounds and ordered prices, and the standard zero endpoints, the original problem (11.52)–(11.56) and the displayed extended model (11.57)–(11.67) have attained minima of the same value:

∃w∗,q∗:w∗∈argmin⁡w∈XC(w),q∗∈argmin⁡q∈proj⁡QC(q),C(w∗)=C(q∗).\exists w^*,q^*:\quad w^*\in\operatorname{argmin}_{w\in X}C(w),\quad q^*\in\operatorname{argmin}_{q\in\operatorname{proj}Q}C(q),\quad C(w^*)=C(q^*).∃w∗,q∗:w∗∈argminw∈X​C(w),q∗∈argminq∈projQ​C(q),C(w∗)=C(q∗).

Here XXX is defined by the original balances, market bounds and setup links, while QQQ is defined by all the printed extended constraints. Each minimum compares against every feasible point of its respective model.

This retains the book's claimed optimization equivalence as the mission goal. F1 gives a one-period counterexample to the printed sales formula, F2 records that the displayed setup domain is binary although the theorem calls the model a linear program, and F4 records the missing boundedness condition for signed storage costs. The claim is therefore expected to be disproved as printed.

Formalization Note The printed αutkl\alpha_{ut}^{kl}αutkl​ in (11.63) and binary domain in (11.67) are retained. No extra market-capacity or balance constraints are imposed on the extension. The standard fixed-endpoint convention is explicit, MMM bounds total potential requirements, and holding/backlog costs remain arbitrary real numbers. No corrected variant replaces this faithful target.

Preamble
import Definitions.Def_PochetWolsey_Variants_CombinedModel
Formal statement
/- Imported module source, reproduced verbatim for declaration-only auditing.
import Mathlib

open scoped BigOperators

namespace PochetWolsey.Variants

structure CombinedData (n K L : ℕ) where
  d : Fin n → ℝ
  V : Fin L → Fin n → ℝ
  p : Fin K → Fin n → ℝ
  q : Fin K → Fin n → ℝ
  e : Fin L → Fin n → ℝ
  h : Fin (n + 1) → ℝ
  b : Fin n → ℝ
  M : ℝ

structure CombinedPoint (n K L : ℕ) where
  x : Fin K → Fin n → ℝ
  y : Fin K → Fin n → ℝ
  v : Fin L → Fin n → ℝ
  s : Fin (n + 1) → ℝ
  r : Fin (n + 1) → ℝ

def CombinedData.Standing {n K L : ℕ} (D : CombinedData n K L) : Prop :=
  0 < n ∧ 0 < K ∧ 0 < L ∧
  (∀ t, 0 ≤ D.d t) ∧ (∀ l t, 0 ≤ D.V l t) ∧
  (∀ k t, 0 ≤ D.p k t ∧ 0 ≤ D.q k t) ∧
  (∀ k j t, k ≤ j → D.q k t ≤ D.q j t ∧ D.p j t ≤ D.p k t) ∧
  (∀ l j t, l ≤ j → D.e j t ≤ D.e l t) ∧
  0 < D.M ∧ (∑ t, (D.d t + ∑ l, D.V l t)) ≤ D.M

noncomputable def CombinedData.Vbar {n K L : ℕ} (D : CombinedData n K L)
    (l : Fin (L + 1)) (t : Fin n) : ℝ :=
  ∑ j ∈ Finset.univ.filter (fun j : Fin L => j.val < l.val), D.V j t

def CombinedPoint.domains {n K L : ℕ} (w : CombinedPoint n K L) : Prop :=
  (∀ k t, 0 ≤ w.x k t ∧ (w.y k t = 0 ∨ w.y k t = 1)) ∧
  (∀ l t, 0 ≤ w.v l t) ∧ (∀ t, 0 ≤ w.s t ∧ 0 ≤ w.r t) ∧
  w.s 0 = 0 ∧ w.s (Fin.last n) = 0 ∧ w.r 0 = 0 ∧ w.r (Fin.last n) = 0

def CombinedData.original {n K L : ℕ} (D : CombinedData n K L)
    (w : CombinedPoint n K L) : Prop :=
  w.domains ∧
  (∀ t : Fin n, w.s t.castSucc - w.r t.castSucc + (∑ k, w.x k t) =
    D.d t + (∑ l, w.v l t) + w.s t.succ - w.r t.succ) ∧
  (∀ l t, w.v l t ≤ D.V l t) ∧ (∀ k t, w.x k t ≤ D.M * w.y k t)

noncomputable def CombinedData.cost {n K L : ℕ} (D : CombinedData n K L)
    (w : CombinedPoint n K L) : ℝ :=
  (∑ k, ∑ t, (D.p k t * w.x k t + D.q k t * w.y k t)) +
    (∑ t, D.h t * w.s t) + (∑ t, D.b t * w.r t.succ) -
    ∑ l, ∑ t, D.e l t * w.v l t

def IsMinimum {A : Type*} (P : A → Prop) (c : A → ℝ) (w : A) : Prop :=
  P w ∧ ∀ w', P w' → c w ≤ c w'

abbrev Allocation (n K L : ℕ) := Fin K → Fin (L + 1) → Fin n → Fin n → ℝ
abbrev Assignment (n K : ℕ) := Fin K → Fin n → Fin n → ℝ

noncomputable def CombinedData.printedExtended {n K L : ℕ} (D : CombinedData n K L)
    (w : CombinedPoint n K L) (α : Allocation n K L) (z : Assignment n K) : Prop :=
  w.domains ∧
  (∀ k l u t, 0 ≤ α k l u t) ∧ (∀ k u t, 0 ≤ z k u t) ∧
  (∀ k u t, z k u t = ∑ l, α k l u t) ∧
  (∀ t, (∑ k, ∑ u, z k u t) = 1) ∧
  (∀ k t, z k t t ≤ w.y k t) ∧
  (∀ (k : Fin K) (u t t' : Fin n), u ≤ t → t'.val = t.val + 1 → z k u t' ≤ z k u t) ∧
  (∀ (k : Fin K) (u t t' : Fin n), t ≤ u → t.val = t'.val + 1 → z k u t' ≤ z k u t) ∧
  (∀ l t, w.v l t = ∑ k, ∑ u,
    ∑ j ∈ Finset.univ.filter (fun j : Fin L => l ≤ j),
      D.V j t * α k l.succ u t) ∧
  (∀ k u, w.x k u = ∑ l, ∑ t, (D.d t + D.Vbar l t) * α k l u t) ∧
  (∀ t : Fin n, w.s t.castSucc = ∑ k, ∑ l,
    ∑ u ∈ Finset.univ.filter (fun u : Fin n => u < t),
      ∑ τ ∈ Finset.univ.filter (fun τ : Fin n => t ≤ τ),
        (D.d τ + D.Vbar l τ) * α k l u τ) ∧
  (∀ t : Fin n, w.r t.succ = ∑ k, ∑ l,
    ∑ u ∈ Finset.univ.filter (fun u : Fin n => t < u),
      ∑ τ ∈ Finset.univ.filter (fun τ : Fin n => τ ≤ t),
        (D.d τ + D.Vbar l τ) * α k l u τ)

noncomputable def CombinedData.extended {n K L : ℕ} (D : CombinedData n K L)
    (w : CombinedPoint n K L) : Prop :=
  ∃ α : Allocation n K L, ∃ z : Assignment n K, D.printedExtended w α z

noncomputable def CombinedData.intervalProduction {n K L : ℕ} (D : CombinedData n K L)
    (w : CombinedPoint n K L) : Prop :=
  ∀ k t, 0 < w.x k t → ∃ a b : Fin n, a ≤ t ∧ t ≤ b ∧
    ∃ S : Fin n → Finset (Fin L),
      w.x k t = ∑ u ∈ Finset.univ.filter (fun u => a ≤ u ∧ u ≤ b),
        (D.d u + ∑ l ∈ S u, D.V l u)

end PochetWolsey.Variants
-/

namespace PochetWolsey.Variants

theorem combined_formulation_solves {n K L : ℕ} (D : CombinedData n K L)
    (hD : D.Standing) :
    ∃ w q : CombinedPoint n K L,
      IsMinimum D.original D.cost w ∧ IsMinimum D.extended D.cost q ∧
      D.cost w = D.cost q := by sorry

end PochetWolsey.Variants
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 357 (PDF 370), Theorem 11.12; DOI 10.1007/0-387-33477-7
Read-back

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

For any natural numbers n,K,Ln, K, Ln,K,L and any data DDD satisfying the standing assumptions below, the statement asserts that there are two points www and qqq with the following properties:

  • www minimizes the cost cDc_DcD​ over the "original" feasible set;
  • qqq minimizes the same cost cDc_DcD​ over the "extended" feasible set;
  • the two minimum values are equal: cD(w)=cD(q)c_D(w) = c_D(q)cD​(w)=cD​(q).

Here "www minimizes ccc over PPP" means that www satisfies PPP, and c(w)≤c(w′)c(w) \le c(w')c(w)≤c(w′) for every w′w'w′ that satisfies PPP. Nothing else links www and qqq. (The point called qqq has nothing to do with the cost coefficients qk,tq_{k,t}qk,t​ in the data.)

Indices and data. Periods are t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}. Stock indices are t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n}. Items are k∈{0,…,K−1}k \in \{0,\dots,K-1\}k∈{0,…,K−1} and l∈{0,…,L−1}l \in \{0,\dots,L-1\}l∈{0,…,L−1}. The data DDD consists of real numbers:

  • demands dtd_tdt​;
  • amounts Vl,tV_{l,t}Vl,t​;
  • coefficients pk,tp_{k,t}pk,t​, qk,tq_{k,t}qk,t​ and el,te_{l,t}el,t​;
  • coefficients hth_tht​ for t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n};
  • coefficients btb_tbt​ for t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1};
  • a constant MMM.

A point www consists of real arrays:

  • xk,tx_{k,t}xk,t​ and yk,ty_{k,t}yk,t​;
  • vl,tv_{l,t}vl,t​;
  • sts_tst​ and rtr_trt​ for t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n}.

Standing assumptions on DDD.

  • n≥1n \ge 1n≥1, K≥1K \ge 1K≥1 and L≥1L \ge 1L≥1.
  • All of dtd_tdt​, Vl,tV_{l,t}Vl,t​, pk,tp_{k,t}pk,t​ and qk,tq_{k,t}qk,t​ are ≥0\ge 0≥0.
  • Whenever k≤jk \le jk≤j: qk,t≤qj,tq_{k,t} \le q_{j,t}qk,t​≤qj,t​ and pj,t≤pk,tp_{j,t} \le p_{k,t}pj,t​≤pk,t​. So qqq is nondecreasing in kkk and ppp is nonincreasing in kkk.
  • Whenever l≤jl \le jl≤j: ej,t≤el,te_{j,t} \le e_{l,t}ej,t​≤el,t​, so eee is nonincreasing in lll.
  • M>0M > 0M>0 and
∑t=0n−1(dt+∑l=0L−1Vl,t)≤M.\sum_{t=0}^{n-1}\Big(d_t + \sum_{l=0}^{L-1} V_{l,t}\Big) \le M.t=0∑n−1​(dt​+l=0∑L−1​Vl,t​)≤M.
  • No sign condition or any other condition is placed on hhh, bbb, or on the sign of eee.

Cost.

cD(w)=∑k∑t=0n−1(pk,txk,t+qk,tyk,t)+∑t=0nhtst+∑t=0n−1bt rt+1−∑l∑t=0n−1el,tvl,t.c_D(w) = \sum_{k}\sum_{t=0}^{n-1}\big(p_{k,t}x_{k,t} + q_{k,t}y_{k,t}\big) + \sum_{t=0}^{n} h_t s_t + \sum_{t=0}^{n-1} b_t\, r_{t+1} - \sum_{l}\sum_{t=0}^{n-1} e_{l,t} v_{l,t}.cD​(w)=k∑​t=0∑n−1​(pk,t​xk,t​+qk,t​yk,t​)+t=0∑n​ht​st​+t=0∑n−1​bt​rt+1​−l∑​t=0∑n−1​el,t​vl,t​.

Domain conditions (part of both feasible sets):

  • xk,t≥0x_{k,t} \ge 0xk,t​≥0 and yk,t∈{0,1}y_{k,t} \in \{0,1\}yk,t​∈{0,1};
  • vl,t≥0v_{l,t} \ge 0vl,t​≥0;
  • st≥0s_t \ge 0st​≥0 and rt≥0r_t \ge 0rt​≥0;
  • s0=sn=0s_0 = s_n = 0s0​=sn​=0 and r0=rn=0r_0 = r_n = 0r0​=rn​=0.

Original feasible set. www satisfies the domain conditions and, for every t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}, every kkk and every lll:

st−rt+∑kxk,t=dt+∑lvl,t+st+1−rt+1,vl,t≤Vl,t,xk,t≤M yk,t.s_t - r_t + \sum_k x_{k,t} = d_t + \sum_l v_{l,t} + s_{t+1} - r_{t+1},\qquad v_{l,t} \le V_{l,t},\qquad x_{k,t} \le M\,y_{k,t}.st​−rt​+k∑​xk,t​=dt​+l∑​vl,t​+st+1​−rt+1​,vl,t​≤Vl,t​,xk,t​≤Myk,t​.

Extended feasible set. www belongs to it when www satisfies the domain conditions and there exist real arrays

  • αk,l,u,t\alpha_{k,l,u,t}αk,l,u,t​ with l∈{0,…,L}l \in \{0,\dots,L\}l∈{0,…,L} and u,t∈{0,…,n−1}u, t \in \{0,\dots,n-1\}u,t∈{0,…,n−1}, and
  • zk,u,tz_{k,u,t}zk,u,t​,

satisfying all of the following:

  1. α≥0\alpha \ge 0α≥0 and z≥0z \ge 0z≥0.

  2. zk,u,t=∑l=0Lαk,l,u,tz_{k,u,t} = \sum_{l=0}^{L} \alpha_{k,l,u,t}zk,u,t​=∑l=0L​αk,l,u,t​.

  3. ∑k∑uzk,u,t=1\sum_k \sum_u z_{k,u,t} = 1∑k​∑u​zk,u,t​=1 for every ttt.

  4. zk,t,t≤yk,tz_{k,t,t} \le y_{k,t}zk,t,t​≤yk,t​.

  5. For u≤tu \le tu≤t with t+1≤n−1t+1 \le n-1t+1≤n−1: zk,u,t+1≤zk,u,tz_{k,u,t+1} \le z_{k,u,t}zk,u,t+1​≤zk,u,t​.

  6. For t≤ut \le ut≤u with t≥1t \ge 1t≥1: zk,u,t−1≤zk,u,tz_{k,u,t-1} \le z_{k,u,t}zk,u,t−1​≤zk,u,t​.

    So, by 5 and 6, zk,u,⋅z_{k,u,\cdot}zk,u,⋅​ is nondecreasing in ttt up to uuu and nonincreasing in ttt from uuu onward.

  7. vl,t=∑k∑u∑j=lL−1Vj,t αk,l+1,u,tv_{l,t} = \sum_k \sum_u \sum_{j=l}^{L-1} V_{j,t}\,\alpha_{k,l+1,u,t}vl,t​=∑k​∑u​∑j=lL−1​Vj,t​αk,l+1,u,t​.

  8. Write Vˉl,t=∑j<lVj,t\bar V_{l,t} = \sum_{j<l} V_{j,t}Vˉl,t​=∑j<l​Vj,t​ for l∈{0,…,L}l \in \{0,\dots,L\}l∈{0,…,L}, so that Vˉ0,t=0\bar V_{0,t} = 0Vˉ0,t​=0. Then

xk,u=∑l=0L∑t(dt+Vˉl,t) αk,l,u,t.x_{k,u} = \sum_{l=0}^{L}\sum_{t}(d_t + \bar V_{l,t})\,\alpha_{k,l,u,t}.xk,u​=l=0∑L​t∑​(dt​+Vˉl,t​)αk,l,u,t​.
  1. For t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}:
st=∑k∑l∑u<t∑τ≥t(dτ+Vˉl,τ) αk,l,u,τ.s_t = \sum_k\sum_l\sum_{u<t}\sum_{\tau \ge t}(d_\tau + \bar V_{l,\tau})\,\alpha_{k,l,u,\tau}.st​=k∑​l∑​u<t∑​τ≥t∑​(dτ​+Vˉl,τ​)αk,l,u,τ​.

No formula is given for sns_nsn​; it is 000 by the domain conditions. 10. For t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}:

rt+1=∑k∑l∑u>t∑τ≤t(dτ+Vˉl,τ) αk,l,u,τ.r_{t+1} = \sum_k\sum_l\sum_{u>t}\sum_{\tau \le t}(d_\tau + \bar V_{l,\tau})\,\alpha_{k,l,u,\tau}.rt+1​=k∑​l∑​u>t∑​τ≤t∑​(dτ​+Vˉl,τ​)αk,l,u,τ​.

The extended set does not explicitly impose the following; they hold only if they follow from the conditions above:

  • the balance equations;
  • vl,t≤Vl,tv_{l,t} \le V_{l,t}vl,t​≤Vl,t​;
  • xk,t≤Myk,tx_{k,t} \le M y_{k,t}xk,t​≤Myk,t​.

The imported definition of "interval production" does not appear in this statement.

Degenerate cases. The standing assumptions exclude n=0n = 0n=0, K=0K = 0K=0 and L=0L = 0L=0, so no index range is empty. There is no division, natural-number subtraction, integral or supremum, so no default values from Lean's total functions arise. Two empty sums occur, and both give 000, consistent with the domain conditions:

  • in condition 9 at t=0t = 0t=0, the sum over u<0u < 0u<0, which matches s0=0s_0 = 0s0​=0;
  • in condition 10 at t=n−1t = n-1t=n−1, the sum over u>n−1u > n-1u>n−1, which matches rn=0r_n = 0rn​=0.

When n=1n = 1n=1, all of sss and rrr are forced to 000, and the original set reduces to ∑kxk,0=d0+∑lvl,0\sum_k x_{k,0} = d_0 + \sum_l v_{l,0}∑k​xk,0​=d0​+∑l​vl,0​ together with the bounds. The statement asserts, for every DDD meeting the standing assumptions, that both feasible sets are nonempty and that cDc_DcD​ attains a minimum on each. This includes data with negative hth_tht​, negative btb_tbt​ or arbitrary-sign el,te_{l,t}el,t​, since no hypothesis restricts them.

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