Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.5 — Lagrangian and convexified decomposition bounds

Disproved
PochetWolsey.Decomposition.lagrangian_convexified_bound

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

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

Let A,bA,bA,b be rational data defining Y={x∈Zn:x≥0,Ax≥b}Y=\{x\in\mathbb Z^n:x\ge0,Ax\ge b\}Y={x∈Zn:x≥0,Ax≥b}. Let D,d,cD,d,cD,d,c be real and set PZ={x≥0:Dx≥d}P_Z=\{x\ge0:Dx\ge d\}PZ​={x≥0:Dx≥d} and H=conv⁡(Y)∩PZH=\operatorname{conv}(Y)\cap P_ZH=conv(Y)∩PZ​. Assume HHH is nonempty and cxcxcx is bounded below on HHH. Let R={x≥0:Bx≥e}=conv⁡(Y)R=\{x\ge0:Bx\ge e\}=\operatorname{conv}(Y)R={x≥0:Bx≥e}=conv(Y) be a tight finite formulation with real data. Define

L(π)=inf⁡y∈Y(cy+π(d−Dy)),w=inf⁡x∈Hcx.L(\pi)=\inf_{y\in Y}\bigl(cy+\pi(d-Dy)\bigr),\qquad w=\inf_{x\in H}cx.L(π)=y∈Yinf​(cy+π(d−Dy)),w=x∈Hinf​cx.

The full column master ranges over all finite convex combinations of points of YYY plus nonnegative combinations of nonzero recession directions u≥0u\ge0u≥0, Au≥0Au\ge0Au≥0, subject to PZP_ZPZ​. Let wcolw_{\rm col}wcol​ be its infimum. Under the preceding section's literal maximum convention, put zLP=sup⁡x∈R∩PZcxz_{LP}=\sup_{x\in R\cap P_Z}cxzLP​=supx∈R∩PZ​​cx. The assertion is

w=max⁡π≥0L(π)=zLP=min⁡x∈Hcx=wcol.w=\max_{\pi\ge0}L(\pi)=z_{LP}=\min_{x\in H}cx=w_{\rm col}.w=π≥0max​L(π)=zLP​=x∈Hmin​cx=wcol​.

There exist a minimizing x∗∈Hx^*\in Hx∗∈H represented in the full master, a maximizing nonnegative multiplier π∗\pi^*π∗, and a point y∗∈Yy^*\in Yy∗∈Y minimizing the Lagrangian at π∗\pi^*π∗. The LP supremum is also asserted to be attained. The convexified optimizer x∗x^*x∗ is not required to lie in YYY.

This identifies the common convexification bound claimed for Lagrangian relaxation, the full column master, and tight reformulation.

Formalization Note The faithful goal retains the maximum definition of the LP bound from p. 198, to which p. 201 explicitly refers. That inherited clause is false (F3); the separately labeled correction uses a minimum. Rationality of A,bA,bA,b makes explicit the rational integer-program convention underlying polyhedrality of the integer hull; c,D,d,B,ec,D,d,B,ec,D,d,B,e remain real. Extended-real infima handle unbounded subproblems without assigning them zero; all finite optimum and multiplier attainments are explicit. The master includes arbitrary recession rays, hence also extreme rays, and permits an empty ray family for bounded cases.

Preamble
import Mathlib
Formal statement
namespace PochetWolsey.Decomposition

theorem lagrangian_convexified_bound {n m q t : ℕ}
    (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 → ℝ) :
    let Y : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
      (∀ i, (b i : ℝ) ≤ ∑ j, (A i j : ℝ) * x j) ∧
      (∀ 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 H := convexHull ℝ Y ∩ PZ
    let PYtight : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
      ∀ i, e i ≤ ∑ j, B i j * x j}
    let cost : (Fin n → ℝ) → ℝ := fun x => ∑ j, c j * x j
    let lag : (Fin q → ℝ) → (Fin n → ℝ) → ℝ := fun π x =>
      cost x + ∑ i, π i * (d i - ∑ j, D i j * x j)
    let L : (Fin q → ℝ) → EReal := fun π =>
      sInf ((fun x => (lag π x : EReal)) '' Y)
    let master : Set (Fin n → ℝ) := {x | x ∈ PZ ∧
      ∃ (k r : ℕ) (v : Fin k → (Fin n → ℝ))
        (u : Fin r → (Fin n → ℝ)) (lam : Fin k → ℝ) (μ : Fin r → ℝ),
        (∀ a, v a ∈ Y) ∧
        (∀ a, u a ≠ 0 ∧ (∀ j, 0 ≤ u a j) ∧
          ∀ i, 0 ≤ ∑ j, (A i j : ℝ) * u a j) ∧
        (∀ a, 0 ≤ lam a) ∧ (∑ a, lam a) = 1 ∧ (∀ a, 0 ≤ μ a) ∧
        x = (fun j => (∑ a, lam a * v a j) + ∑ a, μ a * u a j)}
    let w : EReal := sInf ((fun x => (cost x : EReal)) '' H)
    let zLP : EReal := sSup ((fun x => (cost x : EReal)) '' (PYtight ∩ PZ))
    PYtight = convexHull ℝ Y → H.Nonempty → BddBelow (cost '' H) →
    ∃ (xstar ystar : Fin n → ℝ) (πstar : Fin q → ℝ),
      xstar ∈ H ∧ (∀ x ∈ H, cost xstar ≤ cost x) ∧
      (∀ i, 0 ≤ πstar i) ∧ ystar ∈ Y ∧
      (∀ y ∈ Y, lag πstar ystar ≤ lag πstar y) ∧
      w = (cost xstar : EReal) ∧
      w = L πstar ∧ (∀ π : Fin q → ℝ, (∀ i, 0 ≤ π i) → L π ≤ L πstar) ∧
      w = zLP ∧ w = sInf ((fun x => (cost x : EReal)) '' master) ∧
      xstar ∈ master ∧
      ∃ xmax ∈ PYtight ∩ PZ, (∀ x ∈ PYtight ∩ PZ, cost x ≤ cost xmax) ∧
        zLP = (cost xmax : 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. 201 (PDF 215), Theorem 6.5; Sections 6.3.1–6.3.2, pp. 197–201
Read-back

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

Fix natural numbers n,m,q,tn, m, q, tn,m,q,t and the following data:

  • a rational m×nm \times nm×n matrix AAA and a rational vector b∈Qmb \in \mathbb{Q}^mb∈Qm, both used only after casting their entries to real numbers;
  • a real q×nq \times nq×n matrix DDD and d∈Rqd \in \mathbb{R}^qd∈Rq;
  • a real 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.

All points below live in Rn\mathbb{R}^nRn. The statement defines these sets and functions:

Y={x∈Rn:xj≥0 ∀j,  ∑jAijxj≥bi ∀i,  xj∈Z ∀j},Y = \{x \in \mathbb{R}^n : x_j \ge 0 \ \forall j,\ \ \textstyle\sum_j A_{ij} x_j \ge b_i \ \forall i,\ \ x_j \in \mathbb{Z} \ \forall j\},Y={x∈Rn:xj​≥0 ∀j,  ∑j​Aij​xj​≥bi​ ∀i,  xj​∈Z ∀j},

the nonnegative integer points satisfying Ax≥bAx \ge bAx≥b;

PZ={x:x≥0, Dx≥d},H=conv⁡(Y)∩PZ,PYtight={x:x≥0, Bx≥e},P_Z = \{x : x \ge 0,\ Dx \ge d\}, \qquad H = \operatorname{conv}(Y) \cap P_Z, \qquad P_Y^{\mathrm{tight}} = \{x : x \ge 0,\ Bx \ge e\},PZ​={x:x≥0, Dx≥d},H=conv(Y)∩PZ​,PYtight​={x:x≥0, Bx≥e},

where conv⁡\operatorname{conv}conv is the convex hull in Rn\mathbb{R}^nRn;

cost⁡(x)=∑jcjxj,L(π,x)=cost⁡(x)+∑i=1qπi(di−∑jDijxj)(π∈Rq).\operatorname{cost}(x) = \sum_j c_j x_j, \qquad \mathcal{L}(\pi, x) = \operatorname{cost}(x) + \sum_{i=1}^q \pi_i \Big(d_i - \sum_j D_{ij} x_j\Big) \quad (\pi \in \mathbb{R}^q).cost(x)=j∑​cj​xj​,L(π,x)=cost(x)+i=1∑q​πi​(di​−j∑​Dij​xj​)(π∈Rq).

The following quantities take values in the extended reals [−∞,+∞][-\infty, +\infty][−∞,+∞]:

L(π)=inf⁡y∈YL(π,y),w=inf⁡x∈Hcost⁡(x),zLP=sup⁡x∈PYtight∩PZcost⁡(x).L(\pi) = \inf_{y \in Y} \mathcal{L}(\pi, y), \qquad w = \inf_{x \in H} \operatorname{cost}(x), \qquad z_{LP} = \sup_{x \in P_Y^{\mathrm{tight}} \cap P_Z} \operatorname{cost}(x).L(π)=y∈Yinf​L(π,y),w=x∈Hinf​cost(x),zLP​=x∈PYtight​∩PZ​sup​cost(x).

Note that zLPz_{LP}zLP​ is a supremum, not an infimum.

Finally, MMM ("master") is the set of x∈PZx \in P_Zx∈PZ​ for which there exist:

  • natural numbers k,rk, rk,r;
  • points v1,…,vk∈Yv_1, \dots, v_k \in Yv1​,…,vk​∈Y;
  • vectors u1,…,uru_1, \dots, u_ru1​,…,ur​, each nonzero, each componentwise nonnegative, and each with Aua≥0A u_a \ge 0Aua​≥0;
  • weights λa≥0\lambda_a \ge 0λa​≥0 with ∑aλa=1\sum_a \lambda_a = 1∑a​λa​=1, and μa≥0\mu_a \ge 0μa​≥0;

such that

x=∑a=1kλava+∑a=1rμaua.x = \sum_{a=1}^k \lambda_a v_a + \sum_{a=1}^r \mu_a u_a.x=a=1∑k​λa​va​+a=1∑r​μa​ua​.

Hypotheses. Assume three things:

  1. PYtight=conv⁡(Y)P_Y^{\mathrm{tight}} = \operatorname{conv}(Y)PYtight​=conv(Y) (as sets);
  2. HHH is nonempty;
  3. the real-valued set {cost⁡(x):x∈H}\{\operatorname{cost}(x) : x \in H\}{cost(x):x∈H} is bounded below.

Conclusion. There exist x∗,y∗∈Rnx^\ast, y^\ast \in \mathbb{R}^nx∗,y∗∈Rn and π∗∈Rq\pi^\ast \in \mathbb{R}^qπ∗∈Rq such that all of the following hold:

  • x∗∈Hx^\ast \in Hx∗∈H and cost⁡(x∗)≤cost⁡(x)\operatorname{cost}(x^\ast) \le \operatorname{cost}(x)cost(x∗)≤cost(x) for every x∈Hx \in Hx∈H;
  • πi∗≥0\pi^\ast_i \ge 0πi∗​≥0 for all iii;
  • y∗∈Yy^\ast \in Yy∗∈Y and L(π∗,y∗)≤L(π∗,y)\mathcal{L}(\pi^\ast, y^\ast) \le \mathcal{L}(\pi^\ast, y)L(π∗,y∗)≤L(π∗,y) for every y∈Yy \in Yy∈Y;
  • w=cost⁡(x∗)w = \operatorname{cost}(x^\ast)w=cost(x∗) and w=L(π∗)w = L(\pi^\ast)w=L(π∗);
  • L(π)≤L(π∗)L(\pi) \le L(\pi^\ast)L(π)≤L(π∗) for every π∈Rq\pi \in \mathbb{R}^qπ∈Rq with π≥0\pi \ge 0π≥0;
  • w=zLPw = z_{LP}w=zLP​;
  • w=inf⁡x∈Mcost⁡(x)w = \inf_{x \in M} \operatorname{cost}(x)w=infx∈M​cost(x) (extended-real infimum) and x∗∈Mx^\ast \in Mx∗∈M;
  • there is xmax⁡∈PYtight∩PZx^{\max} \in P_Y^{\mathrm{tight}} \cap P_Zxmax∈PYtight​∩PZ​ with cost⁡(x)≤cost⁡(xmax⁡)\operatorname{cost}(x) \le \operatorname{cost}(x^{\max})cost(x)≤cost(xmax) for all x∈PYtight∩PZx \in P_Y^{\mathrm{tight}} \cap P_Zx∈PYtight​∩PZ​, and zLP=cost⁡(xmax⁡)z_{LP} = \operatorname{cost}(x^{\max})zLP​=cost(xmax).

No relation between x∗x^\astx∗ and y∗y^\asty∗ is asserted. Under hypothesis 1, PYtight∩PZ=HP_Y^{\mathrm{tight}} \cap P_Z = HPYtight​∩PZ​=H. The conclusion w=zLPw = z_{LP}w=zLP​ therefore asserts that the infimum and the supremum of cost⁡\operatorname{cost}cost over the same set HHH coincide and are finite; that is, cost⁡\operatorname{cost}cost is constant on HHH. The conclusion likewise asserts a cost-maximizer xmax⁡x^{\max}xmax on HHH.

Degenerate cases.

  • YYY empty. If Y=∅Y = \emptysetY=∅ (for instance, some bi>0b_i > 0bi​>0 when n=0n = 0n=0, or Ax≥bAx \ge bAx≥b has no nonnegative integer solution), then conv⁡(Y)=∅\operatorname{conv}(Y) = \emptysetconv(Y)=∅. So H=∅H = \emptysetH=∅, hypothesis 2 fails, and the statement is vacuous.
  • n=0n = 0n=0. Here R0\mathbb{R}^0R0 is a single point, all sums over jjj are 000, and YYY is that point exactly when every bi≤0b_i \le 0bi​≤0. No nonzero uau_aua​ exists, so MMM forces r=0r = 0r=0.
  • m=0m = 0m=0. YYY is all of Z≥0n\mathbb{Z}_{\ge 0}^nZ≥0n​, and the ray condition Aua≥0Au_a \ge 0Aua​≥0 is empty.
  • q=0q = 0q=0. PZP_ZPZ​ is the nonnegative orthant, L(π,x)=cost⁡(x)\mathcal{L}(\pi, x) = \operatorname{cost}(x)L(π,x)=cost(x), and π\piπ ranges over the single empty vector, so L(π∗)=inf⁡Ycost⁡L(\pi^\ast) = \inf_Y \operatorname{cost}L(π∗)=infY​cost.
  • t=0t = 0t=0. PYtightP_Y^{\mathrm{tight}}PYtight​ is the nonnegative orthant, so hypothesis 1 demands conv⁡(Y)=R≥0n\operatorname{conv}(Y) = \mathbb{R}^n_{\ge 0}conv(Y)=R≥0n​.
  • kkk and rrr in MMM. In MMM, k≥1k \ge 1k≥1 is forced by ∑aλa=1\sum_a \lambda_a = 1∑a​λa​=1, while r=0r = 0r=0 is allowed.
  • Extended-real conventions. In the extended reals, L(π)=+∞L(\pi) = +\inftyL(π)=+∞ if YYY is empty and L(π)=−∞L(\pi) = -\inftyL(π)=−∞ if L(π,⋅)\mathcal{L}(\pi, \cdot)L(π,⋅) is unbounded below on YYY. Also, zLP=+∞z_{LP} = +\inftyzLP​=+∞ if cost⁡\operatorname{cost}cost is unbounded above on PYtight∩PZP_Y^{\mathrm{tight}} \cap P_ZPYtight​∩PZ​, and zLP=−∞z_{LP} = -\inftyzLP​=−∞ if that set is empty. The conclusions w=L(π∗)=zLP=cost⁡(x∗)w = L(\pi^\ast) = z_{LP} = \operatorname{cost}(x^\ast)w=L(π∗)=zLP​=cost(x∗), however, assert that all of these values are the same finite real number.
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