Theorem 5.1 — the adaptability gap is at most four
ProvedRobustPower.AdaptGap.theorem_5_1_robust_le_four_adaptLet and . Let , and let every scenario have and . Both decision stages may have designated nonnegative integer coordinates. If the paired uncertainty set is symmetric, then the optimal static robust cost is at most four times the optimal fully adaptive worst-case cost:
This is the paper's constant-factor bound when uncertainty affects both right-hand sides and second-stage costs, including mixed-integer second-stage decisions.
Formalization Note Both values are extended-real infima over exactly the feasible decisions in (1.5)–(1.6); no optimal-solution attainment is assumed. Symmetry makes the scenario set nonempty and bounded. Integer coordinates are designated by sets, equivalent to the paper's product domains up to coordinate relabelling.
import Mathlib import Definitions.Def_RobustPower_AdaptGap_Problems
namespace RobustPower.AdaptGap
/-- Theorem 5.1, p. 28: the adaptability gap is at most four. -/
theorem theorem_5_1_robust_le_four_adapt {m n₁ n₂ : ℕ} {Ω : Type*}
(A : Matrix (Fin m) (Fin n₁) ℝ) (B : Matrix (Fin m) (Fin n₂) ℝ)
(b : Ω → Fin m → ℝ) (c : Fin n₁ → ℝ) (d : Ω → Fin n₂ → ℝ)
(I₁ : Set (Fin n₁)) (I₂ : Set (Fin n₂))
(hc : 0 ≤ c) (hb : ∀ ω, 0 ≤ b ω) (hd : ∀ ω, 0 ≤ d ω)
(hsym : RobustPower.StochGap.IsSymmetric (scenarioSet b d)) :
zRob A B b c d I₁ I₂ ≤ (4 : EReal) * zAdapt A B b c d I₁ I₂ := by sorry
end RobustPower.AdaptGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.