Theorem 2.4 — is the deterministic problem with the worst right-hand side
ProvedRobustPower.Hypercube.theorem_2_4_robust_eq_deterministicmixed-integer-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let , , , , let be the integer coordinates of the first stage, and let the second-stage variables be continuous (). Let be a nonempty scenario set with right-hand sides that are bounded above, and let
Then:
- a pair is feasible for the robust problem (1.2) if and only if it is feasible for the deterministic problem : , , ;
- consequently .
The robust problem, with one constraint block per scenario, is thus a single mixed integer program whose size does not depend on the uncertainty set. The same worst-scenario principle, applied to all the data at once, drives Theorem 5.4.
Formalization Note Values are extended-real infima, so the equality also covers infeasible problems. The paper's is a supremum here; boundedness above of the right-hand sides replaces its attainment, so the statement contains the paper's case.
Preamble
import Definitions.Def_RobustPower_Hypercube_RhsProblems
Formal statement
namespace RobustPower.Hypercube
/-- Theorem 2.4 (p. 17): with `bʰ` the coordinatewise maximum of the right-hand
sides, a pair `(x, y)` is feasible for `Π_Rob(b)` exactly when it is feasible for
the deterministic problem `Π` with right-hand side `bʰ`, and `z_Rob(b) = z(Π)`.
The second-stage variables are continuous (`p₂ = 0`, `I₂ = ∅`), as in `Π` on the page. -/
theorem theorem_2_4_robust_eq_deterministic
{m n₁ n₂ : ℕ} {Ω : Type*} [Nonempty Ω]
(A : Matrix (Fin m) (Fin n₁) ℝ) (B : Matrix (Fin m) (Fin n₂) ℝ)
(b : Ω → Fin m → ℝ) (I₁ : Set (Fin n₁))
(c : Fin n₁ → ℝ) (d : Fin n₂ → ℝ)
(hc : 0 ≤ c) (hd : 0 ≤ d) (hb : ∀ ω, 0 ≤ b ω)
(hbdd : BddAbove (Set.range b)) :
(∀ (x : Fin n₁ → ℝ) (y : Fin n₂ → ℝ),
robFeasibleRhs A B b I₁ ∅ x y ↔ detFeasible A B (worstRhs b) I₁ ∅ x y) ∧
zRobRhs A B b I₁ ∅ c d = zDet A B (worstRhs b) I₁ ∅ c d := by sorry
end RobustPower.Hypercube
Source
Bertsimas & Goyal, On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems, authors' manuscript (MIT DSpace) of Math. Oper. Res. DOI 10.1287/moor.1090.0440, p. 17, Theorem 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.