TITLE: Uncertainty Quantification for Optimization Models and Batch Solution Methods

Abstract

In most optimization models, the input parameters are uncertain estimates derived from data. Existing approaches in optimization focus on finding one optimal decision, to perform well on average, or to guarantee a worst-case performance under uncertainty. Although making a single decision given data is key to the operation of any system, additional insights as to how uncertain such solution might be is also important in decision-making. The intuition classical sensitivity analysis can provide is limited for complex systems because there can be a large number of input parameters. We propose a computational framework to empirically estimate the uncertainty by solving the optimization problem for sampled input parameters. In this talk, we focus on solving linear programs (LPs) with varying parameters.

The common approach is solving the LPs for all combinations of given parameter values, called the brute-force, which can be computationally infeasible when the parameter space is high-dimensional and/or the underlying LP is computationally challenging. We introduce a new approach for solving a large number of LPs that differ only in the right hand side of the constraints ($\bb$ of $\A x= \bb$). The computational approach builds on theoretical properties of the geometry of the space of critical regions, where a critical region is defined as the set of $\bb$'s for which a basis is optimal. To formally support our computational approach we provide proofs of geometric properties of neighboring critical regions. While these theoretical properties have been stated and applied in the existing literature of parametric programming, their formal proofs have not been provided to the best of our knowledge. Based on the geometric properties of critical regions, we develop an algorithm that solves the LPs in batches by finding critical regions that contain multiple $\bb$'s. Moreover, we suggest a data-driven version of our algorithm that uses the distribution (e.g., shape) of a sample of $\bb$'s for which the LPs need to be solved. The experimental results on a benchmark problem show that our approach can be more efficient and scale better in the number of $\bb$'s than the brute-force, but also indicate some limitations of the algorithm. Possible extensions of the method are also discussed.

Bio

Dr. Lee is a postdoc researcher in our department working with Dr. Serban. His research interests are in health data analytics and large-scale optimization problems arising in data analytics. He is applying his expertise in operations research and machine learning to translating large-scale health data into recommendations for policy makers and to develop novel approaches for solving optimization problems in healthcare applications.