Title:

From Disjoint Bilinear Optimization to Affine Policies in Dynamic Robust Optimization

Abstract:

Affine policies are widely used as a solution approach in dynamic robust 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. This work aims to address this stark-contrast between the worst-case and the empirical performance of affine policies.
In particular, we study the performance of affine policies for a two-stage adjustable robust optimization problem under 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 matching the hardness of approximation for this class of uncertainty sets. Our analysis is based on first designing an LP based approximation for a general disjoint bilinear optimization problem over packing polytopes (the separation problem for our two-stage problem). Based on this, we present an LP-restriction for the two-stage problem that we relate to affine policies  and show that it gives an $O(\log n \log L/(\log\log n \log\log L))$-approximation (where $n$ is the number of decision variables, and $L$ is the number of budget constraints describing the uncertainty set). This significantly improves over prior known bounds for the performance of affine policies and nearly matches the hardness of approximation. As a byproduct, we also obtain a significantly faster LP to compute near-optimal affine policies.
This talk is based on joint work with Ayoub Foussoul and 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 healthcare. He received the 2021 INFORMS Revenue Management and Pricing Section prize and 2019 MSOM Society Best Paper in Operations Research Prize. His research has been supported by grants from NSF, DARPA and the industry including the NSF CAREER Award and faculty research awards from Google, IBM, Adobe and Amazon.