Static vs. Adjustable Solutions in Dynamic Optimization


Vineet Goyal
Columbia University IEOR

Wednesday, Oct.22, 2014
4:15 - 5:15 PM
Huang 305


Abstract:

We consider a two-stage robust linear optimization problem with uncertain packing constraints. These arise in many applications including resource allocation and scheduling with uncertain resource requirements. An adjustable or a dynamic solution specifies the solution for each possible uncertain second-stage scenario; computing an optimal adjustable solution is often intractable. On the other hand, a static solution is a single solution feasible for all second-stage scenarios; it can be computed efficiently in most cases. However, a static solution is believed to be highly conservative as compared to an adjustable solution. We give a tight characterization of the performance of static solutions for the two-stage linear optimization problem with uncertain packing constraints and give a bound the adaptivity gap. In particular, we show that for a fairly general class of uncertainty sets, a static solution is optimal. 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 the geometric properties of the uncertainty set. This work shows that a static solution provides a good approximation for the adjustable robust linear optimization problem for a broad class of uncertainty sets.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html