ORIE Colloquium: Omar El Housni (Columbia) - From affine to threshold policies: a new framework in dynamic robust optimization

Description

In many sequential decision problems, uncertainty is revealed over time and we need to make decisions in the face of uncertainty. This is a fundamental problem arising in many applications such as facility location, resource allocation and capacity planning under demand uncertainty. Robust optimization is an approach to model uncertainty where we optimize over the worst-case realization of parameters within an uncertainty set. While computing an optimal solution in dynamic robust optimization is usually intractable, affine policies (or linear decision rules) are widely used as an approximate solution approach. However, there is a stark contrast between the observed good empirical performance and the bad worst-case theoretical performance bounds. In this talk, we address this stark contrast between theory and practice. We introduce a probabilistic approach to analyze the performance of affine policies on randomly generated instances and show they are near-optimal with high probability under reasonable assumptions. We also study these policies under important models of uncertainty such as budget of uncertainty sets and show that affine policies give an optimal approximation matching the hardness of approximation. Furthermore, based on insights from this analysis, we design new tractable policies for dynamic robust optimization, namely piecewise affine and threshold policies, that are scalable and improve significantly over affine policies in many settings.

Bio:
Omar El Jousni a Ph.D. candidate in operations research at Columbia University, advised by Prof. Vineet Goyal. He is broadly interested in decision-making under uncertainty where he aims to develop optimization models and algorithms to address a wide-range of operational problems. His current research focuses on the design of robust and efficient algorithms for sequential dynamic optimization problems under uncertainty with applications in inventory management, facility location and matching platforms. Prior to joining Columbia, El Housni graduated from Ecole Polytechnique (Paris) with an M.S. and B.S. in applied mathematics.