Proof of Theorem 1, p. 9 — due to (B1), the master optimal value z̄ is a lower bound on the optimal value of (6)
ProvedLogicBenders.Generic.master_lower_boundbenders-decompositionlogic-based-benderslower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1valid-cuts
Let problem (6) be given by and . Let be bounding functions each satisfying (B1): for every feasible of (6). If is an optimal solution, with optimal value , of the master problem (9) with these cuts,
then
This is the lower-bound half of the proof of Theorem 1: the master relaxes (6), because every valid cut is satisfied by every feasible solution of (6).
Formalization Note. A master optimum means and for every ; the value (an unbounded master) is allowed. Cuts are numbered from .
Preamble
import Mathlib import Definitions.Def_LogicBenders_Generic_Setting
Formal statement
namespace LogicBenders.Generic
theorem master_lower_bound {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) :
z ≤ optVal S f := by sorry
end LogicBenders.Generic
Source
Hooker & Ottosson, Logic-based Benders decomposition, revised manuscript (Nov. 2000), p. 9, proof of Theorem 1, sixth sentence; master problem (9), p. 8; (B1), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.