De-Risking Solutions to Optimization Problems
Optimal or near-optimal solutions to real-world optimization problems tend to exhibit what might be termed ‘concentration’ of actions or of deployed resources. This is due to the nature of the task at hand (i.e., optimization) which conspires with flexibility present in real systems. Thus, as a simple example, in an optimal solution to a logistical problem we might see heavy usage of a certain combination of routes by large vehicles. Such concentrations are a source of risk — they represent a focused point of failure which the optimization problem was not tasked to protect from.
In principle, one could try to contain concentration by imposing ‘capacities’ on features at risk; however, there may well be too many such potential features and it is not even clear, a priori, what the capacities should be.
In this talk we present a strategy to address these issues that stems, in part, from an attitude frequently found among real-world stakeholders; namely that the overt imposition of a risk structure in the optimization task is, often, anathema — it amounts to prioritizing conservatism over solution performance.
Rather than attempting to solve, directly, a risk-aware problem (e.g., a stochastic or robust optimization problem) we describe a rapid procedure that either (a) adjusts a given optimal solution so as to substantially reduce its risk while, also, not substantially increasing cost, or (b) demonstrates that (a) is not possible. Our procedure relies on first-order concepts and a cutting-plane algorithm. We describe numerical experiments at scale.
Joint work with Blake Sisson (Columbia) and Remi Akinwonmi and Alexandra Newman (Colorado School of Mines).
Bio: Daniel Bienstock is Liu Family Professor of Operations Research at Columbia University, with a joint appointment in Applied Math and a courtesy appointment in Electrical Engineering. He received his Ph.D. in operations research from MIT. His work focuses on methodology and computational aspects of optimization, with additional focus on large-scale applications of optimization in engineering domains.