Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 11.3 — an optimal interval-production solution

Disproved
PochetWolsey.Variants.optimal_interval_production

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

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

For the combined uncapacitated model with KKK production types and LLL sales markets, under the stated nonnegative-demand, market-bound, cost-ordering, and standard endpoint conventions, there exists an optimal feasible solution with the following property. Whenever xtk>0x_t^k>0xtk​>0, there are periods a≤t≤ba\le t\le ba≤t≤b and market subsets S(u)⊆{1,…,L}S(u)\subseteq\{1,\dots,L\}S(u)⊆{1,…,L} such that

xtk=∑u=ab(du+∑l∈S(u)Vul).x_t^k=\sum_{u=a}^b\left(d_u+\sum_{l\in S(u)}V_u^l\right).xtk​=u=a∑b​​du​+l∈S(u)∑​Vul​​.

This is the structural observation preceding the extended formulation. The assertion includes existence and attainment of an optimum, not merely an implication about a hypothetical minimizer.

Formalization Note Interval endpoints replace the book's offsets t−a,t+bt-a,t+bt−a,t+b and are constrained to the horizon. The subsets may depend on the production type and period under consideration. As printed, holding and backlog costs have no sign condition; F4 records the resulting failure of optimal-solution existence.

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 optimal_interval_production {n K L : ℕ} (D : CombinedData n K L)
    (hD : D.Standing) :
    ∃ w : CombinedPoint n K L, IsMinimum D.original D.cost w ∧
      D.intervalProduction w := by sorry

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

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

Let n,K,L∈Nn, K, L \in \mathbb{N}n,K,L∈N, and let DDD be data consisting of:

  • d∈Rnd \in \mathbb{R}^nd∈Rn;
  • V,e∈RL×nV, e \in \mathbb{R}^{L\times n}V,e∈RL×n;
  • p,q∈RK×np, q \in \mathbb{R}^{K\times n}p,q∈RK×n;
  • h∈Rn+1h \in \mathbb{R}^{n+1}h∈Rn+1 (entries h0,…,hnh_0,\dots,h_nh0​,…,hn​);
  • b∈Rnb \in \mathbb{R}^nb∈Rn;
  • M∈RM \in \mathbb{R}M∈R.

Indices ttt, kkk and lll range over periods {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}, machines {0,…,K−1}\{0,\dots,K-1\}{0,…,K−1} and classes {0,…,L−1}\{0,\dots,L-1\}{0,…,L−1} respectively, in natural order.

Assume the standing condition:

  • n,K,L>0n, K, L > 0n,K,L>0;
  • d≥0d \ge 0d≥0, V≥0V \ge 0V≥0, p≥0p \ge 0p≥0, and q≥0q \ge 0q≥0 entrywise;
  • 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​ whenever k≤jk \le jk≤j;
  • ej,t≤el,te_{j,t} \le e_{l,t}ej,t​≤el,t​ whenever l≤jl \le jl≤j;
  • M>0M > 0M>0;
  • ∑t(dt+∑lVl,t)≤M\sum_t\big(d_t + \sum_l V_{l,t}\big) \le M∑t​(dt​+∑l​Vl,t​)≤M.

No condition is placed on the signs of hhh, bbb or eee.

Points www consist of x,y∈RK×nx, y \in \mathbb{R}^{K\times n}x,y∈RK×n, v∈RL×nv \in \mathbb{R}^{L\times n}v∈RL×n, and s,r∈Rn+1s, r \in \mathbb{R}^{n+1}s,r∈Rn+1. Such a point is original-feasible when all of the following hold:

  • x≥0x \ge 0x≥0 and y∈{0,1}K×ny \in \{0,1\}^{K\times n}y∈{0,1}K×n;
  • v≥0v \ge 0v≥0;
  • s,r≥0s, r \ge 0s,r≥0;
  • s0=sn=r0=rn=0s_0 = s_n = r_0 = r_n = 0s0​=sn​=r0​=rn​=0;
  • for each t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}:
st−rt+∑kxk,t=dt+∑lvl,t+st+1−rt+1;s_t - r_t + \sum_k x_{k,t} = d_t + \sum_l v_{l,t} + s_{t+1} - r_{t+1};st​−rt​+k∑​xk,t​=dt​+l∑​vl,t​+st+1​−rt+1​;
  • 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 cost of www is

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

The theorem asserts that there exists a point www with both of the following properties.

  1. www minimizes cost. www is original-feasible, and c(w)≤c(w′)c(w) \le c(w')c(w)≤c(w′) for every original-feasible point w′w'w′. In particular, this asserts that the original-feasible set is nonempty and that ccc attains its infimum on it.
  2. www has interval production. For every k,tk, tk,t with xk,t>0x_{k,t} > 0xk,t​>0, there are periods a≤t≤ba \le t \le ba≤t≤b and arbitrary subsets Su⊆{0,…,L−1}S_u \subseteq \{0,\dots,L-1\}Su​⊆{0,…,L−1}, one per period uuu, such that
xk,t=∑u=ab(du+∑l∈SuVl,u).x_{k,t} = \sum_{u=a}^{b}\Big(d_u + \sum_{l\in S_u} V_{l,u}\Big).xk,t​=u=a∑b​(du​+l∈Su​∑​Vl,u​).

The sets SuS_uSu​ need not be initial segments of the classes, and they are not required to match www's vvv.

Degenerate cases. The standing condition excludes n=0n = 0n=0, K=0K = 0K=0 and L=0L = 0L=0. It permits:

  • n=1n = 1n=1: then sss and rrr are identically 000, and the balance equation reads ∑kxk,0=d0+∑lvl,0\sum_k x_{k,0} = d_0 + \sum_l v_{l,0}∑k​xk,0​=d0​+∑l​vl,0​;
  • d≡0d \equiv 0d≡0 and V≡0V \equiv 0V≡0;
  • negative entries of hhh, bbb and eee.

The cost does not depend on h0h_0h0​ or hnh_nhn​, because s0=sn=0s_0 = s_n = 0s0​=sn​=0. Interval production is vacuous at every (k,t)(k, t)(k,t) with xk,t=0x_{k,t} = 0xk,t​=0.

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