Proof of Theorem 1, p. 9 — if the subproblem dual is infeasible, the subproblem is unbounded, and so (6) is unbounded
ProvedLogicBenders.Generic.unbounded_of_dual_infeasiblebenders-decompositioninference-dualitylogic-based-bendersp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1unbounded
Let problem (6) be given by and , and let . Suppose the subproblem dual (8) at is infeasible: no real number satisfies . Then
- the subproblem (7) is unbounded: for every real there is with and ;
- problem (6) is unbounded: for every real there is with .
This is the third clause of the proof of Theorem 1.
Formalization Note. "Infeasible" means that no real is feasible. The value is always trivially feasible, so the infeasibility of the dual cannot be stated over the extended reals.
Preamble
import Mathlib import Definitions.Def_LogicBenders_Generic_Setting
Formal statement
namespace LogicBenders.Generic
theorem unbounded_of_dual_infeasible {X Y : Type*} (S : Set (X × Y)) (f : X → Y → ℝ) (yb : Y)
(h : ¬ ∃ β : ℝ, IsDualFeasible S f yb (β : EReal)) :
(∀ M : ℝ, ∃ x : X, (x, yb) ∈ S ∧ f x yb < M) ∧ IsUnbounded S f := by sorry
end LogicBenders.Generic
Source
Hooker & Ottosson, Logic-based Benders decomposition, revised manuscript (Nov. 2000), p. 9, proof of Theorem 1, third paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.