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 adaptive or a dynamic solution specifies the solution for each possible uncertain second-stage scenario; computing an optimal adaptive solution is often intractable. On the other hand, a static solution (a single solution feasible for all second-stage scenarios) can be computed efficiently but is believed to be highly conservative. 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 additivity 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 show that the static solution gives nearly the best possible approximation for the adjustable robust problem under some reasonable assumptions.

This is joint work with Pranjal Awasthi and Brian Lu.