Static vs Adjustable Solutions in Dynamic Optimization

We study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable, but a static solution can be computed efficiently in most cases. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear optimization problem. Furthermore, when a static solution is not optimal, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set.