On the Optimality of Affine Decision Rules in Robust and Distributionally Robust Optimization

We propose tight conditions under which two-stage robust and distributionally robust optimization problems are optimally solved in affine decision rules. Contrary to previous work, our conditions do not impose any structure on the support of the uncertain problem parameters, and they ensure point-wise (as opposed to worst-case) optimality of affine decision rules. The absence of support restrictions allows us to consider rich classes of uncertainty sets as well as transfer non-linearities to the support via liftings, while the point-wise optimality ensures that decision rules remain optimal for broad classes of distributionally robust optimization problems, including data-driven problems over $\phi$-divergence or Wasserstein ambiguity sets. We show that our conditions are met by problems in diverse application domains, such as logistics, inventory and supply chain management, flexible production planning and healthcare scheduling. We also show how problems that `almost’ meet our conditions can sometimes be solved by complementing affine decision rules with methods that isolate the complicating problem structure.

Article

Download

View PDF