Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6.4 — equivalent formulation bounds (printed convention)

Disproved
PochetWolsey.Decomposition.formulation_bounds

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

decompositioninteger-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1polyhedra

Let PY={x≥0:Ax≥b}P_Y=\{x\ge0:Ax\ge b\}PY​={x≥0:Ax≥b} have rational data, let Y=PY∩ZnY=P_Y\cap\mathbb Z^nY=PY​∩Zn, and let PZ={x≥0:Dx≥d}P_Z=\{x\ge0:Dx\ge d\}PZ​={x≥0:Dx≥d}. All dimensions are finite; ccc and the linking data are real. Let R={x≥0:Bx≥e}R=\{x\ge0:Bx\ge e\}R={x≥0:Bx≥e} and E={x≥0:∃v∈Rp,Fx+Gv≥g}E=\{x\ge0:\exists v\in\mathbb R^p, Fx+Gv\ge g\}E={x≥0:∃v∈Rp,Fx+Gv≥g} be tight descriptions: R=E=conv⁡(Y)R=E=\operatorname{conv}(Y)R=E=conv(Y). For a finite family of cuts aix≥ria_i x\ge r_iai​x≥ri​ valid on YYY, put C=PY∩PZ∩{x:aix≥ri}C=P_Y\cap P_Z\cap\{x:a_i x\ge r_i\}C=PY​∩PZ​∩{x:ai​x≥ri​}.

An exact separator returns no cut precisely at points of conv⁡(Y)\operatorname{conv}(Y)conv(Y); every returned cut is valid for YYY and strictly violated by the query point. Assume the cutting-plane run has terminated at a minimizer xˉ\bar xxˉ over CCC where that separator returns no cut. Write S1=R∩PZS_1=R\cap P_ZS1​=R∩PZ​, S2=E∩PZS_2=E\cap P_ZS2​=E∩PZ​, and S3=CS_3=CS3​=C. With the preceding paragraph's literal convention zi=sup⁡x∈Sicxz_i=\sup_{x\in S_i}cxzi​=supx∈Si​​cx, the printed assertion is

z1=z2=z3=min⁡x∈conv⁡(Y)∩PZcx.z_1=z_2=z_3=\min_{x\in\operatorname{conv}(Y)\cap P_Z}cx.z1​=z2​=z3​=x∈conv(Y)∩PZ​min​cx.

All three suprema and the minimum are asserted to be attained. This records the source's comparison of direct formulations, projections, and completed cutting-plane relaxations.

Formalization Note This faithful item is false: the page defines each ziz_izi​ by maximization but equates it to a minimum. Finding F1 gives Y={0,1}Y=\{0,1\}Y={0,1}, all three sets [0,1][0,1][0,1], and c=1c=1c=1. Values use extended reals to avoid default real infima; the finite minimum is explicitly witnessed. Exact separation is encoded by its oracle specification and terminal-state conditions, without assuming that the finite cut region equals the hull.

Preamble
import Mathlib
Formal statement
namespace PochetWolsey.Decomposition

theorem formulation_bounds {n m q t p a s : ℕ}
    (A : Matrix (Fin m) (Fin n) ℚ) (b : Fin m → ℚ)
    (D : Matrix (Fin q) (Fin n) ℝ) (d : Fin q → ℝ)
    (c : Fin n → ℝ)
    (B : Matrix (Fin t) (Fin n) ℝ) (e : Fin t → ℝ)
    (F : Matrix (Fin a) (Fin n) ℝ) (G : Matrix (Fin a) (Fin p) ℝ)
    (g : Fin a → ℝ)
    (cuts : Matrix (Fin s) (Fin n) ℝ) (rhs : Fin s → ℝ)
    (sep : (Fin n → ℝ) → Option ((Fin n → ℝ) × ℝ)) :
    let PY : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
      ∀ i, (b i : ℝ) ≤ ∑ j, (A i j : ℝ) * x j}
    let Y : Set (Fin n → ℝ) := {x | x ∈ PY ∧ ∀ j, ∃ z : ℤ, x j = (z : ℝ)}
    let PZ : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
      ∀ i, d i ≤ ∑ j, D i j * x j}
    let direct : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
      ∀ i, e i ≤ ∑ j, B i j * x j}
    -- The auxiliary sum over Fin p remains even when the original dimension n is zero.
    let Q : Set ((Fin n → ℝ) × (Fin p → ℝ)) := {xv |
      (∀ j, 0 ≤ xv.1 j) ∧
      ∀ i, g i ≤ (∑ j, F i j * xv.1 j) + ∑ j, G i j * xv.2 j}
    let projection : Set (Fin n → ℝ) := {x | ∃ v : Fin p → ℝ, (x, v) ∈ Q}
    let cutting : Set (Fin n → ℝ) := {x | x ∈ PY ∩ PZ ∧
      ∀ i, rhs i ≤ ∑ j, cuts i j * x j}
    let cost : (Fin n → ℝ) → ℝ := fun x => ∑ j, c j * x j
    let value : Set (Fin n → ℝ) → EReal := fun S =>
      sSup ((fun x => (cost x : EReal)) '' S)
    direct = convexHull ℝ Y → projection = convexHull ℝ Y →
    (∀ i, ∀ y ∈ Y, rhs i ≤ ∑ j, cuts i j * y j) →
    (∀ x, sep x = none ↔ x ∈ convexHull ℝ Y) →
    (∀ x α β, sep x = some (α, β) →
      (∀ y ∈ Y, β ≤ ∑ j, α j * y j) ∧ (∑ j, α j * x j) < β) →
    (∃ xbar ∈ cutting, (∀ x ∈ cutting, cost xbar ≤ cost x) ∧ sep xbar = none) →
    value (direct ∩ PZ) = value (projection ∩ PZ) ∧
    value (projection ∩ PZ) = value cutting ∧
    value cutting = sInf ((fun x => (cost x : EReal)) '' (convexHull ℝ Y ∩ PZ)) ∧
    (∀ S ∈ [direct ∩ PZ, projection ∩ PZ, cutting],
      ∃ xmax ∈ S, (∀ x ∈ S, cost x ≤ cost xmax) ∧ value S = (cost xmax : EReal)) ∧
    ∃ xstar ∈ convexHull ℝ Y ∩ PZ,
      (∀ x ∈ convexHull ℝ Y ∩ PZ, cost xstar ≤ cost x) ∧
      sInf ((fun x => (cost x : EReal)) '' (convexHull ℝ Y ∩ PZ)) =
        (cost xstar : EReal) := by sorry

end PochetWolsey.Decomposition
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, DOI 10.1007/0-387-33477-7, p. 198 (PDF 212), Proposition 6.4; Section 6.3.1, pp. 197–198
Read-back

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

Data. Fix natural numbers n,m,q,t,p,a,sn, m, q, t, p, a, sn,m,q,t,p,a,s, any of which may be 000. Vectors x∈Rnx \in \mathbb{R}^nx∈Rn are indexed by j=1,…,nj = 1,\dots,nj=1,…,n. The theorem takes:

  • a rational m×nm \times nm×n matrix AAA and a rational vector b∈Qmb \in \mathbb{Q}^mb∈Qm, both used only after conversion to reals;
  • a real q×nq \times nq×n matrix DDD and d∈Rqd \in \mathbb{R}^qd∈Rq;
  • a cost vector c∈Rnc \in \mathbb{R}^nc∈Rn;
  • a real t×nt \times nt×n matrix BBB and e∈Rte \in \mathbb{R}^te∈Rt;
  • real matrices FFF (a×na \times na×n) and GGG (a×pa \times pa×p), and g∈Rag \in \mathbb{R}^ag∈Ra;
  • a real s×ns \times ns×n matrix CCC (named cuts) and r∈Rsr \in \mathbb{R}^sr∈Rs (named rhs);
  • an arbitrary function σ\sigmaσ (named sep). For each x∈Rnx \in \mathbb{R}^nx∈Rn, σ(x)\sigma(x)σ(x) either returns "none" or returns a pair (α,β)(\alpha, \beta)(α,β) with α∈Rn\alpha \in \mathbb{R}^nα∈Rn and β∈R\beta \in \mathbb{R}β∈R.

Sets defined. All inequalities between vectors below are componentwise.

PY={x∈Rn:x≥0, Ax≥b},Y={x∈PY:xj∈Z for every j},P_Y = \{x \in \mathbb{R}^n : x \ge 0,\ Ax \ge b\}, \qquad Y = \{x \in P_Y : x_j \in \mathbb{Z} \text{ for every } j\},PY​={x∈Rn:x≥0, Ax≥b},Y={x∈PY​:xj​∈Z for every j}, PZ={x:x≥0, Dx≥d},Direct={x:x≥0, Bx≥e},P_Z = \{x : x \ge 0,\ Dx \ge d\}, \qquad \text{Direct} = \{x : x \ge 0,\ Bx \ge e\},PZ​={x:x≥0, Dx≥d},Direct={x:x≥0, Bx≥e}, Q={(x,v)∈Rn×Rp:x≥0, Fx+Gv≥g}.Q = \{(x,v) \in \mathbb{R}^n \times \mathbb{R}^p : x \ge 0,\ Fx + Gv \ge g\}.Q={(x,v)∈Rn×Rp:x≥0, Fx+Gv≥g}.

In QQQ the auxiliary vector vvv has no sign constraint.

Proj={x:∃v∈Rp, (x,v)∈Q},Cut={x∈PY∩PZ:Cx≥r}.\text{Proj} = \{x : \exists v \in \mathbb{R}^p,\ (x,v) \in Q\}, \qquad \text{Cut} = \{x \in P_Y \cap P_Z : Cx \ge r\}.Proj={x:∃v∈Rp, (x,v)∈Q},Cut={x∈PY​∩PZ​:Cx≥r}.

The cost is cost⁡(x)=∑jcjxj\operatorname{cost}(x) = \sum_j c_j x_jcost(x)=∑j​cj​xj​. For a set S⊆RnS \subseteq \mathbb{R}^nS⊆Rn, define

val⁡(S)=sup⁡{cost⁡(x):x∈S}∈[−∞,+∞].\operatorname{val}(S) = \sup\{\operatorname{cost}(x) : x \in S\} \in [-\infty, +\infty].val(S)=sup{cost(x):x∈S}∈[−∞,+∞].

This is a supremum taken in the extended reals.

Hypotheses. Write conv⁡Y\operatorname{conv} YconvY for the real convex hull of YYY.

  1. Direct=conv⁡Y\text{Direct} = \operatorname{conv} YDirect=convY.
  2. Proj=conv⁡Y\text{Proj} = \operatorname{conv} YProj=convY.
  3. Every y∈Yy \in Yy∈Y satisfies Cy≥rCy \ge rCy≥r.
  4. For every xxx: σ(x)\sigma(x)σ(x) is "none" if and only if x∈conv⁡Yx \in \operatorname{conv} Yx∈convY.
  5. Whenever σ(x)=(α,β)\sigma(x) = (\alpha, \beta)σ(x)=(α,β), two things hold:
    • β≤α⋅y\beta \le \alpha \cdot yβ≤α⋅y for all y∈Yy \in Yy∈Y;
    • α⋅x<β\alpha \cdot x < \betaα⋅x<β.
  6. There exists xˉ∈Cut\bar x \in \text{Cut}xˉ∈Cut such that:
    • cost⁡(xˉ)≤cost⁡(x)\operatorname{cost}(\bar x) \le \operatorname{cost}(x)cost(xˉ)≤cost(x) for all x∈Cutx \in \text{Cut}x∈Cut, so xˉ\bar xxˉ is a cost minimizer over Cut;
    • σ(xˉ)\sigma(\bar x)σ(xˉ) is "none".

Conclusions. All five hold together.

  1. val⁡(Direct∩PZ)=val⁡(Proj∩PZ)\operatorname{val}(\text{Direct} \cap P_Z) = \operatorname{val}(\text{Proj} \cap P_Z)val(Direct∩PZ​)=val(Proj∩PZ​).
  2. val⁡(Proj∩PZ)=val⁡(Cut)\operatorname{val}(\text{Proj} \cap P_Z) = \operatorname{val}(\text{Cut})val(Proj∩PZ​)=val(Cut).
  3. The supremum of cost over Cut equals the infimum of cost over conv⁡Y∩PZ\operatorname{conv} Y \cap P_ZconvY∩PZ​:
sup⁡x∈Cutcost⁡(x)=inf⁡{cost⁡(x):x∈conv⁡Y∩PZ}.\sup_{x \in \text{Cut}} \operatorname{cost}(x) = \inf\{\operatorname{cost}(x) : x \in \operatorname{conv} Y \cap P_Z\}.x∈Cutsup​cost(x)=inf{cost(x):x∈convY∩PZ​}.
  1. Each of the three sets S∈{Direct∩PZ, Proj∩PZ, Cut}S \in \{\text{Direct} \cap P_Z,\ \text{Proj} \cap P_Z,\ \text{Cut}\}S∈{Direct∩PZ​, Proj∩PZ​, Cut} contains a point xmax⁡x_{\max}xmax​ such that:
    • cost⁡(x)≤cost⁡(xmax⁡)\operatorname{cost}(x) \le \operatorname{cost}(x_{\max})cost(x)≤cost(xmax​) for all x∈Sx \in Sx∈S, so xmax⁡x_{\max}xmax​ is a cost maximizer on SSS;
    • val⁡(S)=cost⁡(xmax⁡)\operatorname{val}(S) = \operatorname{cost}(x_{\max})val(S)=cost(xmax​).
  2. There exists x⋆∈conv⁡Y∩PZx^\star \in \operatorname{conv} Y \cap P_Zx⋆∈convY∩PZ​ such that:
    • cost⁡(x⋆)≤cost⁡(x)\operatorname{cost}(x^\star) \le \operatorname{cost}(x)cost(x⋆)≤cost(x) for all x∈conv⁡Y∩PZx \in \operatorname{conv} Y \cap P_Zx∈convY∩PZ​;
    • inf⁡{cost⁡(x):x∈conv⁡Y∩PZ}=cost⁡(x⋆)\inf\{\operatorname{cost}(x) : x \in \operatorname{conv} Y \cap P_Z\} = \operatorname{cost}(x^\star)inf{cost(x):x∈convY∩PZ​}=cost(x⋆).

No boundedness assumption on the cost over any of these sets appears among the hypotheses.

Degenerate cases. Hypothesis 6 makes Cut nonempty. By hypothesis 4 the point xˉ\bar xxˉ lies in conv⁡Y\operatorname{conv} YconvY, so YYY and conv⁡Y∩PZ\operatorname{conv} Y \cap P_ZconvY∩PZ​ are nonempty. If YYY were empty, hypothesis 4 would force σ(xˉ)≠\sigma(\bar x) \neσ(xˉ)= "none", and the hypotheses could not all hold. Whenever the hypotheses cannot hold simultaneously, the statement is vacuously true. The defaults that would otherwise apply are: the supremum of the empty set is −∞-\infty−∞ and the infimum of the empty set is +∞+\infty+∞.

The zero-size cases are as follows:

  • n=0n = 0n=0. R0\mathbb{R}^0R0 is a single point and every sum over jjj is 000, so the cost is identically 000. PYP_YPY​ is that point exactly when b≤0b \le 0b≤0; similarly PZP_ZPZ​ requires d≤0d \le 0d≤0 and Direct requires e≤0e \le 0e≤0. Cut requires r≤0r \le 0r≤0, and Proj requires some vvv with Gv≥gGv \ge gGv≥g. Integrality is vacuous, so Y=PYY = P_YY=PY​.
  • m=0m = 0m=0. PYP_YPY​ is the nonnegative orthant and YYY is the set of all nonnegative integer vectors.
  • q=0q = 0q=0. PZP_ZPZ​ is the nonnegative orthant.
  • t=0t = 0t=0. Direct is the nonnegative orthant.
  • a=0a = 0a=0. Proj is the nonnegative orthant.
  • p=0p = 0p=0. Proj is {x≥0:Fx≥g}\{x \ge 0 : Fx \ge g\}{x≥0:Fx≥g}.
  • s=0s = 0s=0. Hypothesis 3 is vacuous and Cut=PY∩PZ\text{Cut} = P_Y \cap P_ZCut=PY​∩PZ​.

Since cost takes only real values, val⁡(S)\operatorname{val}(S)val(S) for a nonempty SSS is either a real number or +∞+\infty+∞. Conclusion 4 nevertheless asserts that a maximizer exists on each of the three sets.

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