Theorem 1, p. 9 — with valid cuts (B1), a terminated generic Benders run ends optimal with value z̄, infeasible, or unbounded
ProvedLogicBenders.Generic.theorem_1Consider problem (6), subject to , , , with real-valued, and a run of the generic Benders algorithm (Figure 1): start from and an initial ; while the subproblem dual (8) at has a feasible solution , formulate a bounding function with and add the Benders cut to the master problem (9); if the master is infeasible, stop; otherwise let be an optimal solution of the master with optimal value , and repeat.
Suppose that in each iteration the bounding function satisfies
(B1) the Benders cut is valid: every feasible solution of (6) satisfies .
Then:
- If the algorithm terminates with a finite optimal solution of the master problem, then (6) has an optimal solution with value :
- If it terminates with an infeasible master problem, then (6) is infeasible: .
- If it terminates with an infeasible subproblem dual, then (6) is unbounded: for every real some has .
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 ; a run through iterations starts with and, at each iteration , passes the While test, adds a cut equal to at , and takes as a master optimum for exactly the cuts . Each clause assumes (B1) for exactly the cuts its run has added: cuts in clauses 1 and 3, cuts in clause 2. "Finite" is (the master value is by definition of a master optimum). "Infeasible subproblem dual" means no real is dual-feasible. Clause 1 carries one hypothesis not printed in the theorem: if the optimal value of the subproblem (7) at the terminal is finite, it is attained. The proof on p. 9 asserts exactly this ("the subproblem primal (7) has optimal value and some optimal solution "), and without it clause 1 is false: with , a single point, , and the valid cut , the run stops with and (6) has no optimal solution. The hypothesis holds automatically when is finite.
import Mathlib import Definitions.Def_LogicBenders_Generic_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.