Skip to main content

Robust Optimization

Robust optimization asks for performance across every value in a declared uncertainty set. It does not require a full probability distribution, but the protection claim is only as credible as the set.

Prerequisites​

Complete stochastic optimization.

Learning goals​

  • Define an uncertainty set with units and provenance.
  • Compare nominal, stochastic, and worst-case objectives.
  • Measure a price of robustness against a named nominal reference.
  • Avoid turning a deterministic set guarantee into an unsupported probability claim.

Protection set and counterpart​

For the delivery instance, use the componentwise box

dE∈[4,10],dW∈[4,9].d_E\in[4,10],\qquad d_W\in[4,9].

For a fixed plan, worst-case shortfall occurs at the upper corner because the penalty is monotone in both demands. Enumerating feasible route plans therefore gives a transparent robust counterpart for this small problem.

This box does not assert that every east/west combination is jointly plausible, nor that demand falls inside with 95% probability. A box may be conservative precisely because it protects simultaneous extremes. Budgeted, polyhedral, or ellipsoidal sets encode different beliefs and produce different decisions.

Worked example​

from itertools import product

def cost(plan, demand):
route_a, route_b = plan
east_capacity = 4 * route_a + route_b
west_capacity = route_a + 4 * route_b
shortage = max(0, demand[0] - east_capacity) + max(0, demand[1] - west_capacity)
return 80 * route_a + 70 * route_b + 50 * shortage

plans = [(a, b) for a, b in product(range(4), repeat=2)
if a + b <= 3 and 5 * a + 4 * b <= 14]
upper_corner = (10, 9)
robust = min(plans, key=lambda plan: (cost(plan, upper_corner), plan))
sample_average = (2, 1)
nominal = (7, 6)
price = cost(robust, nominal) - cost(sample_average, nominal)
print("uncertainty_set=east[4,10] west[4,9] joint_coverage_claim=False")
print(f"robust_plan=(route_a={robust[0]},route_b={robust[1]}) worst_case_cost_eur={cost(robust, upper_corner)}")
print(f"sample_average_worst_case_cost_eur={cost(sample_average, upper_corner)} nominal_price_of_robustness_eur={price}")

Expected output:

uncertainty_set=east[4,10] west[4,9] joint_coverage_claim=False
robust_plan=(route_a=1,route_b=2) worst_case_cost_eur=420
sample_average_worst_case_cost_eur=430 nominal_price_of_robustness_eur=40

The robust plan improves the declared box worst case by EUR 10 but costs EUR 40 more at the base demand. That difference is the reported price of robustness for this reference—not a universal property of robust planning.

Limitations and common mistakes​

  • Widening a set mechanically can make a solution uselessly conservative; narrowing it without evidence hides risk.
  • Componentwise bounds ignore correlation and may combine mutually implausible extremes.
  • Robust feasibility for modeled constraints does not cover omitted constraints, implementation errors, or changing operations.
  • Compare policies on common out-of-sample cases; do not select the set on the final test cases and then call the result validation.

Practice​

Replace the box with the three observed planning scenarios only. Recompute the worst-case plan and state exactly which demand pairs are no longer protected.

Next steps​

Estimate noisy policy performance using shared random streams in simulation-based optimization.

Primary sources​

Checked 2026-10-19: Bertsimas and Sim, The Price of Robustness and the author-hosted paper; Boyd and Vandenberghe, Convex Optimization.