TITLE: On the Power of Affine Policies in Two-stage Adjustable Robust Optimization



Affine policies are widely used as a solution approach in dynamic optimization where computing an optimal adjustable solution is usually intractable. While the worst case

performance of affine policies can be significantly bad, the empirical performance is observed to be near-optimal for a large class of problem instances. For instance, in the two-stage dynamic robust optimization problem with linear covering constraints and uncertain right hand side, the worst-case approximation bound for affine policies is O(√m) that is also tight (see Bertsimas and Goyal [8]), whereas observed empirical performance is near-optimal. This work aims to address this stark-contrast between the worst-case and the empirical performance of affine policies. 


We show that affine policies are provably a good approximation for the two-stage adjustable robust optimization problem with high probability on random instances

where the constraint coefficients are generated i.i.d. from a large class of distributions; thereby, providing a theoretical justification of the observed empirical performance. We also consider the performance of affine policies for an important class of uncertainty sets, namely the budget of uncertainty and intersection of budget of uncertainty sets. We show that surprisingly affine policies provide nearly the best possible approximation for this class of uncertainty sets that matches the hardness of approximation; further confirming the power of affine policies.


This talk is based is joint work with my student Omar El Housni.


BIO: Vineet Goyal is Associate Professor in the Industrial Engineering and Operations Research Department at Columbia University where he joined in 2010. He received his Bachelor's degree in Computer Science from Indian Institute of Technology, Delhi in 2003 and his Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University in 2008. Before coming to Columbia, he spent two years as a Postdoctoral Associate at the Operations Research Center at MIT. He is interested in the design of efficient and robust data-driven algorithms for large scale dynamic optimization problems with applications in  revenue management and smart grid problems. His research has been continually supported by grants from NSF and industry including NSF CAREER Award in 2014 and faculty research awards from Google, IBM and Adobe.