Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Observation 10.3 — detecting an interval with no setups

Proved
PochetWolsey.BacklogStartup.no_setup_interval

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

backlogginglot-sizingp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planningstart-up-costs

Let y,zy,zy,z be an exact binary setup and start-up plan satisfying (10.5)–(10.8), with given y0∈{0,1}y_0\in\{0,1\}y0​∈{0,1}. For periods 1≤k<t≤n1\le k<t\le n1≤k<t≤n,

yk+∑j=k+1tzj=0⟺yk=yk+1=⋯=yt=0.y_k+\sum_{j=k+1}^t z_j=0\quad\Longleftrightarrow\quad y_k=y_{k+1}=\cdots=y_t=0.yk​+j=k+1∑t​zj​=0⟺yk​=yk+1​=⋯=yt​=0.

Thus an initial setup and the subsequent start-ups together detect whether any setup occurs in the interval. This observation underlies the stock inequalities used in the joint formulation.

Initial-state convention: the parameter y0 is the same fixed binary datum in every feasible set in this item (printed p. 138 / PDF 155); it is not optimized.

Preamble
import Mathlib
import Definitions.Def_PochetWolsey_BacklogStartup_StartupModel
Formal statement
namespace PochetWolsey.BacklogStartup

theorem no_setup_interval {n : ℕ} (y0 : ℝ) (hy0 : y0 = 0 ∨ y0 = 1) (y z : Fin n → ℝ) (h : ExactStartup y0 y z)
    (k t : ℕ) (hk : 1 ≤ k) (hkt : k < t) (ht : t ≤ n) :
    (period y k + ∑ j ∈ Finset.Icc (k + 1) t, period z j) = 0 ↔
      ∀ j ∈ Finset.Icc k t, period y j = 0 := by sorry

end PochetWolsey.BacklogStartup
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 321 (PDF 334), Observation 10.3
Read-back

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

Setting. Let n∈Nn \in \mathbb{N}n∈N and let y0y^0y0 be a real number with y0=0y^0 = 0y0=0 or y0=1y^0 = 1y0=1. Let y,z∈Rny, z \in \mathbb{R}^ny,z∈Rn, with coordinates y1,…,yny_1,\dots,y_ny1​,…,yn​ and z1,…,znz_1,\dots,z_nz1​,…,zn​. Write:

  • vˉt=vt\bar v_t = v_tvˉt​=vt​ for 1≤t≤n1 \le t \le n1≤t≤n, and 000 otherwise;
  • y^0=y0\hat y_0 = y^0y^​0​=y0 and y^t=yˉt\hat y_t = \bar y_ty^​t​=yˉ​t​ for t≥1t \ge 1t≥1.

Hypotheses on yyy and zzz. Assume the exact startup conditions:

  • every yt∈{0,1}y_t \in \{0,1\}yt​∈{0,1};
  • every zt∈{0,1}z_t \in \{0,1\}zt​∈{0,1};
  • for every t∈{1,…,n}t \in \{1,\dots,n\}t∈{1,…,n}:
yt−y^t−1≤zt,zt≤yt,zt≤1−y^t−1.y_t - \hat y_{t-1} \le z_t, \qquad z_t \le y_t, \qquad z_t \le 1 - \hat y_{t-1}.yt​−y^​t−1​≤zt​,zt​≤yt​,zt​≤1−y^​t−1​.

Claim. Let k,t∈Nk, t \in \mathbb{N}k,t∈N with 1≤k<t≤n1 \le k < t \le n1≤k<t≤n. Then

yk+∑j=k+1tzj=0⟺yj=0 for every j∈{k,k+1,…,t}.y_k + \sum_{j=k+1}^{t} z_j = 0 \quad\Longleftrightarrow\quad y_j = 0 \text{ for every } j \in \{k, k+1, \dots, t\}.yk​+j=k+1∑t​zj​=0⟺yj​=0 for every j∈{k,k+1,…,t}.

All indices involved lie in 1..n1..n1..n, so no zero-extension values enter.

Degenerate cases.

  • The hypotheses 1≤k<t≤n1 \le k < t \le n1≤k<t≤n force n≥2n \ge 2n≥2. For n≤1n \le 1n≤1, no such k,tk, tk,t exist and the statement is vacuous.
  • The interval has at least two periods, so the sum on the left contains at least one zzz-term.
  • The value of y0y^0y0 enters only through the hypotheses at t=1t = 1t=1, and in particular through the constraint on z1z_1z1​. Since k≥1k \ge 1k≥1, z1z_1z1​ never appears in the sum.
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