Proof of Theorem 1, p. 9 — the subproblem value at any trial ȳ is an upper bound on the optimal value of (6)
ProvedLogicBenders.Generic.subVal_upper_boundbenders-decompositionlogic-based-bendersp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1upper-bound
Let and define problem (6), over . For any trial value , the optimal value of the subproblem (7) obtained by fixing is at least the optimal value of (6):
In the proof of Theorem 1 this is the remark that , the optimal value of the last subproblem, is an upper bound on the optimal value of (6).
Formalization Note. Both values are taken in ; when the subproblem is infeasible its value is and the inequality is immediate.
Preamble
import Mathlib import Definitions.Def_LogicBenders_Generic_Setting
Formal statement
namespace LogicBenders.Generic
theorem subVal_upper_bound {X Y : Type*} (S : Set (X × Y)) (f : X → Y → ℝ) (yb : Y) :
optVal S f ≤ subVal S f yb := by sorry
end LogicBenders.Generic
Source
Hooker & Ottosson, Logic-based Benders decomposition, revised manuscript (Nov. 2000), p. 9, proof of Theorem 1, fourth sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.