Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 12.5 — two-setup sequence characterization

Proved
PochetWolsey.Modes.two_mode_binary

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

convex-hullp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planningset-up-sequences

Let YM2−SCY^{M2-SC}YM2−SC consist of setup/startup pairs generated by nonempty repetition-free lists of at most two labels per period, with the last label of one period first in the next. It equals the binary constraint set

∑i(yi(t)−zi(t))=1,∑izi(t)≤1,zi(t)≤yi(t),\sum_i(y_i(t)-z_i(t))=1,\qquad \sum_i z_i(t)\le1,\qquad z_i(t)\le y_i(t),i∑​(yi​(t)−zi​(t))=1,i∑​zi​(t)≤1,zi​(t)≤yi​(t), zi(t+1)≥yi(t+1)−yi(t),zi(t+1)+zi(t)≤yi(t+1),z_i(t+1)\ge y_i(t+1)-y_i(t),\qquad z_i(t+1)+z_i(t)\le y_i(t+1),zi​(t+1)≥yi​(t+1)−yi​(t),zi​(t+1)+zi​(t)≤yi​(t+1),

where the last two inequalities apply between adjacent periods. This is an equality of discrete feasible sets, not a convex-hull assertion.

Formalization Note There are m+1m+1m+1 labels, including idle label 000, and n+1n+1n+1 periods, numbered 0,…,n0,\ldots,n0,…,n. Thus m=n=0m=n=0m=n=0 means one idle label and one period, not empty index sets. The initial setup is unrestricted. Eliminating its one-hot value with zero initial startup leaves the displayed first-period conditions; no terminal continuation is prescribed.

Preamble
import Mathlib
Formal statement
namespace PochetWolsey.Modes

theorem two_mode_binary (m n : ℕ) :
    {p : (Fin (m + 1) → Fin (n + 1) → ℝ) × (Fin (m + 1) → Fin (n + 1) → ℝ) | ∃ s : Fin (n + 1) → List (Fin (m + 1)),
      (∀ t, s t ≠ [] ∧ (s t).Nodup) ∧
      (∀ t : Fin n, (s t.castSucc).getLast? = (s t.succ).head?) ∧ (∀ t, (s t).length ≤ 2) ∧ p = ((fun i t => if i ∈ s t then (1 : ℝ) else 0), (fun i t => if i ∈ (s t).tail then (1 : ℝ) else 0))} =
    {p | (∀ i, (∀ t, p.1 i t = 0 ∨ p.1 i t = 1)) ∧ (∀ i, (∀ t, p.2 i t = 0 ∨ p.2 i t = 1)) ∧
    (∀ t, ∑ i, (p.1 i t - p.2 i t) = 1) ∧
    (∀ t, ∑ i, p.2 i t ≤ 1) ∧
    (∀ i t, p.2 i t ≤ p.1 i t) ∧
    (∀ i (t : Fin n), p.2 i t.succ ≥ p.1 i t.succ - p.1 i t.castSucc) ∧
    (∀ i (t : Fin n), p.2 i t.succ + p.2 i t.castSucc ≤ p.1 i t.succ)} := by sorry

end PochetWolsey.Modes
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 379 (PDF 390), Proposition 12.5
Read-back

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

For every pair of natural numbers m,nm,nm,n, this theorem asserts an equality of two sets of pairs (x,y)(x,y)(x,y) of real arrays. Both arrays are indexed by an item i∈Im={0,…,m}i \in I_m = \{0,\dots,m\}i∈Im​={0,…,m} and a period t∈{0,…,n}t \in \{0,\dots,n\}t∈{0,…,n}. The claim is a plain set equality, not a convex-hull statement.

The left-hand side. It is the set of pairs for which there exists an assignment sss of a finite list of items sts_tst​ to each period ttt satisfying all of the following.

  1. Each sts_tst​ is nonempty and has no repeated entries.
  2. For each t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}, the last entry of sts_tst​ equals the first entry of st+1s_{t+1}st+1​.
  3. Each sts_tst​ has length at most 222.
  4. xi,t=1x_{i,t} = 1xi,t​=1 if iii occurs in sts_tst​, and 000 otherwise.
  5. yi,t=1y_{i,t} = 1yi,t​=1 if iii occurs in sts_tst​ after removing its first entry, and 000 otherwise.

Given conditions 1 and 3, the list sts_tst​ is either:

  • [a][a][a], which gives y⋅,t=0y_{\cdot,t} = 0y⋅,t​=0; or
  • [a,b][a,b][a,b] with a≠ba \ne ba=b, which gives yb,t=1y_{b,t} = 1yb,t​=1 and all other entries of y⋅,ty_{\cdot,t}y⋅,t​ equal to 000.

The right-hand side. It is the set of pairs such that:

  • every xi,tx_{i,t}xi,t​ and every yi,ty_{i,t}yi,t​ is 000 or 111;
  • for every period ttt:
∑i∈Im(xi,t−yi,t)=1,∑i∈Imyi,t≤1;\sum_{i \in I_m} (x_{i,t} - y_{i,t}) = 1,\qquad \sum_{i \in I_m} y_{i,t} \le 1;i∈Im​∑​(xi,t​−yi,t​)=1,i∈Im​∑​yi,t​≤1;
  • for all i,ti,ti,t: yi,t≤xi,ty_{i,t} \le x_{i,t}yi,t​≤xi,t​;
  • for all iii and every t∈{0,…,n−1}t \in \{0,\dots,n-1\}t∈{0,…,n−1}:
yi,t+1≥xi,t+1−xi,t,yi,t+1+yi,t≤xi,t+1.y_{i,t+1} \ge x_{i,t+1} - x_{i,t},\qquad y_{i,t+1} + y_{i,t} \le x_{i,t+1}.yi,t+1​≥xi,t+1​−xi,t​,yi,t+1​+yi,t​≤xi,t+1​.

No inequality bounds yi,0y_{i,0}yi,0​ from below in terms of xxx. Period 000 enters the transition inequalities only as the earlier period.

Claim. The theorem asserts that the left-hand set equals the right-hand set, with both inclusions.

Degenerate cases.

  • n=0n = 0n=0. There is a single period, and every transition condition on both sides is vacuous.
    • The left side is the set of indicator pairs of a single list of one item or of two distinct items.
    • The right side is the set of binary pairs satisfying the three per-period conditions.
  • m=0m = 0m=0. The only admissible list is [0][0][0], so the left side is the single point x≡1x \equiv 1x≡1, y≡0y \equiv 0y≡0. On the right side, x0,t−y0,t=1x_{0,t} - y_{0,t} = 1x0,t​−y0,t​=1 with binary entries forces the same values.
  • Sums over items are never empty.
  • No junk values. No default-valued operation occurs.
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