Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 9 — with valid cuts (B1), a terminated generic Benders run ends optimal with value z̄, infeasible, or unbounded

Proved
LogicBenders.Generic.theorem_1

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

benders-decompositioncorrectnessinference-dualitylogic-based-bendersp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1valid-cuts

Consider problem (6), min⁡f(x,y)\min f(x,y)minf(x,y) subject to (x,y)∈S(x,y)\in S(x,y)∈S, x∈Dxx\in D_xx∈Dx​, y∈Dyy\in D_yy∈Dy​, with fff real-valued, and a run of the generic Benders algorithm (Figure 1): start from zˉ=−∞\bar z = -\inftyzˉ=−∞ and an initial yˉ∈Dy\bar y\in D_yyˉ​∈Dy​; while the subproblem dual (8) at yˉ\bar yyˉ​ has a feasible solution β>zˉ\beta > \bar zβ>zˉ, formulate a bounding function βyˉ\beta_{\bar y}βyˉ​​ with βyˉ(yˉ)=β\beta_{\bar y}(\bar y) = \betaβyˉ​​(yˉ​)=β and add the Benders cut z≥βyˉ(y)z \ge \beta_{\bar y}(y)z≥βyˉ​​(y) to the master problem (9); if the master is infeasible, stop; otherwise let (zˉ,yˉ)(\bar z,\bar y)(zˉ,yˉ​) be an optimal solution of the master with optimal value zˉ\bar zzˉ, and repeat.

Suppose that in each iteration the bounding function satisfies

(B1) the Benders cut z≥βyˉ(y)z \ge \beta_{\bar y}(y)z≥βyˉ​​(y) is valid: every feasible solution (x,y)(x,y)(x,y) of (6) satisfies f(x,y)≥βyˉ(y)f(x,y) \ge \beta_{\bar y}(y)f(x,y)≥βyˉ​​(y).

Then:

  1. If the algorithm terminates with a finite optimal solution (z,y)=(zˉ,yˉ)(z,y) = (\bar z,\bar y)(z,y)=(zˉ,yˉ​) of the master problem, then (6) has an optimal solution (x,y)=(xˉ,yˉ)(x,y) = (\bar x,\bar y)(x,y)=(xˉ,yˉ​) with value f(xˉ,yˉ)=zˉf(\bar x,\bar y) = \bar zf(xˉ,yˉ​)=zˉ:
(xˉ,yˉ)∈S,f(xˉ,yˉ)=zˉ,f(xˉ,yˉ)≤f(x,y)  for all (x,y)∈S.(\bar x,\bar y)\in S,\qquad f(\bar x,\bar y) = \bar z,\qquad f(\bar x,\bar y)\le f(x,y)\ \text{ for all } (x,y)\in S.(xˉ,yˉ​)∈S,f(xˉ,yˉ​)=zˉ,f(xˉ,yˉ​)≤f(x,y)  for all (x,y)∈S.
  1. If it terminates with an infeasible master problem, then (6) is infeasible: S=∅S = \varnothingS=∅.
  2. If it terminates with an infeasible subproblem dual, then (6) is unbounded: for every real MMM some (x,y)∈S(x,y)\in S(x,y)∈S has f(x,y)<Mf(x,y) < Mf(x,y)<M.

Theorem 1 is the correctness theorem of logic-based Benders decomposition: whatever inference method produces the cuts, validity of the cuts alone guarantees that the algorithm's three ways of stopping report the right answer.

Formalization Note. Iterations are numbered from 000; a run through NNN iterations starts with zˉ0=−∞\bar z_0 = -\inftyzˉ0​=−∞ and, at each iteration k<Nk < Nk<N, passes the While test, adds a cut equal to βk\beta_kβk​ at yˉk\bar y_kyˉ​k​, and takes (zˉk+1,yˉk+1)(\bar z_{k+1},\bar y_{k+1})(zˉk+1​,yˉ​k+1​) as a master optimum for exactly the cuts 0,…,k0,\dots,k0,…,k. Each clause assumes (B1) for exactly the cuts its run has added: cuts 0,…,N−10,\dots,N-10,…,N−1 in clauses 1 and 3, cuts 0,…,N0,\dots,N0,…,N in clause 2. "Finite" is zˉN≠−∞\bar z_N \neq -\inftyzˉN​=−∞ (the master value is <+∞< +\infty<+∞ by definition of a master optimum). "Infeasible subproblem dual" means no real β\betaβ is dual-feasible. Clause 1 carries one hypothesis not printed in the theorem: if the optimal value of the subproblem (7) at the terminal yˉ\bar yyˉ​ is finite, it is attained. The proof on p. 9 asserts exactly this ("the subproblem primal (7) has optimal value β∗\beta^*β∗ and some optimal solution xˉ\bar xxˉ"), and without it clause 1 is false: with Dx=RD_x = \mathbb RDx​=R, DyD_yDy​ a single point, S={x>0}S = \{x > 0\}S={x>0}, f(x,y)=xf(x,y) = xf(x,y)=x and the valid cut 000, the run stops with zˉ=0\bar z = 0zˉ=0 and (6) has no optimal solution. The hypothesis holds automatically when DxD_xDx​ is finite.

Preamble
import Mathlib
import Definitions.Def_LogicBenders_Generic_Setting
Formal statement
namespace LogicBenders.Generic

theorem theorem_1 {X Y : Type*} (S : Set (X × Y)) (f : X → Y → ℝ) (r : Run Y) (N : ℕ) :
    -- (i) termination with a finite optimal solution `(z̄, ȳ)` of the master problem
    (StopsAtWhile S f r N →
      (∀ k < N, ValidCut S f (r.cut k)) →
      r.zbar N ≠ ⊥ →
      -- attainment of the subproblem (7) at the terminal `ȳ` when its value is finite
      -- (asserted in the proof on p. 9: "some optimal solution x̄")
      (subVal S f (r.ybar N) ≠ ⊤ → subVal S f (r.ybar N) ≠ ⊥ →
        ∃ x : X, (x, r.ybar N) ∈ S ∧ (f x (r.ybar N) : EReal) = subVal S f (r.ybar N)) →
      ∃ xbar : X, (xbar, r.ybar N) ∈ S ∧ (f xbar (r.ybar N) : EReal) = r.zbar N ∧
        ∀ (x : X) (y : Y), (x, y) ∈ S → f xbar (r.ybar N) ≤ f x y) ∧
    -- (ii) termination with an infeasible master problem
    (StopsAtMaster S f r N →
      (∀ k ≤ N, ValidCut S f (r.cut k)) →
      S = ∅) ∧
    -- (iii) termination with an infeasible subproblem dual
    (StopsAtWhile S f r N →
      (∀ k < N, ValidCut S f (r.cut k)) →
      (¬ ∃ β : ℝ, IsDualFeasible S f (r.ybar N) (β : EReal)) →
      IsUnbounded S f) := by sorry

end LogicBenders.Generic
Source
Hooker & Ottosson, Logic-based Benders decomposition, revised manuscript (Nov. 2000), p. 9, Theorem 1 and Figure 1
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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