Proof of Theorem 1, p. 9 — when the algorithm terminates at a master optimum (z̄, ȳ), the subproblem dual value β* equals z̄
ProvedLogicBenders.Generic.beta_star_eq_zbarLet problem (6) be given by and , let be bounding functions satisfying (B1), and let be an optimal solution, with value , of the master problem (9) with these cuts. Suppose the generic Benders algorithm terminates at , i.e. the While test of Figure 1 fails: the subproblem dual (8) at has no feasible solution . Then the optimal value of the subproblem dual (8), and the optimal value of the subproblem (7), both equal :
This is the step "because the algorithm terminated with a finite solution, " of the proof of Theorem 1.
Formalization Note. The page assumes the master solution is finite; the equality holds without that assumption (including ), so the hypothesis is dropped and the statement is stronger. Both the dual value (the page's quantity) and the primal subproblem value are stated.
import Mathlib import Definitions.Def_LogicBenders_Generic_Setting
namespace LogicBenders.Generic
theorem beta_star_eq_zbar {X Y : Type*} (S : Set (X × Y)) (f : X → Y → ℝ)
(cut : ℕ → Y → EReal) (k : ℕ) (hB1 : ∀ j ≤ k, ValidCut S f (cut j))
(z : EReal) (yb : Y) (h : IsMasterOptimal cut k z yb)
(hstop : ¬ ∃ β : EReal, IsDualFeasible S f yb β ∧ z < β) :
subDualVal S f yb = z ∧ subVal S f yb = z := by sorry
end LogicBenders.Generic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.