Thursday 3 June 2021

Chair

  • Frits Spieksma – Eindhoven University of Technology
  • Dick den Hertog – Tilburg University

Robust Optimization (RO) aims to generate solutions to optimization problems that are good for a wide range of realizations of parameter values. On one hand, RO has proven to be a very fruitful methodology allowing to protect a decision maker against uncertainty. On the other hand, there are still many fields where the use of advanced RO techniques may have a positive impact on the stability of solutions used. In this track, different aspects of Robust Optimization, both theoretical and applied, will be discussed; we trust that ensuing discussion will further advance the field, and hope to meet you at the symposium!

Speakers

Dimitris Bertsimas, Massachusetts Institute of Technology

Title: Robust Optimization with Side Data: A Reproducing Kernel Hilbert Space Approach

Abstract:

We introduce and solve the problem of minimizing a cost function subject to constraints that depend on a vector of  uncertain parameters,  given historical data on the parameters, including side data. We present two methods, based on regression in reproducing kernel Hilbert spaces, for solving an optimization problem with uncertain parameters for which we have historical data, including auxiliary data. The first method approximates the objective function and the second approximates the optimizer. We provide finite sample guarantees and prove asymptotic optimality for both methods. Computational experiments suggest that at least  the second method  overcomes a curse of dimensionality that afflicts existing methods, extrapolates better to unseen data, and achieves a many-fold decrease in sample complexity even for small dimensions. (joint work with Nihal Koduri, MIT).  

Bart Smeulders, Eindhoven University of Technology

Handling uncertainty in Kidney Exchange Problems

Mathematical optimization techniques have established themselves as an important and indispensable tool in guiding decisions in kidney exchange programs. Current formulations and implementations can easily handle deterministic instances of even the largest KEPs. However, there are many sources of uncertainty in kidney exchange. These range from withdrawal of donors to medical incompatibilities revealed after matching and even scheduling conflicts between transplant centres. As a result, a large number of potential transplants identified in the matching fail. For example, in the NHS Living Kidney Sharing Scheme, 30% of identified matches did not proceed to transplant between 2013-2017. The American UNOS program at one point saw a 93% failure rate.

Recent research has focused on handling match failures in kidney exchange. A variety of recourse options, some of which are employed by functioning kidney exchanges, are being studied. In this talk, we look at some of the computational challenges encountered when incorporating uncertainty into kidney exchange.

Sebastian Stiller, TU Braunschweig

Robust Optimization: From timetables to machine learning

Abstract: Robust optimization is an approach to stochastic optimization without stochasticity. In this talk we will take a tour through the development of robust optimization from its basic ideas and results over the challenges and solutions in two-stage robustness until recent results showing the advantages of using robust optimization for reliable machine learning and explainable AI.

In practice, data is almost always uncertain, vague, and corrupted. Looking for solutions that respect the uncertainty of data ex ante yields significantly better results than adjusting deterministic solutions ex post. Stochastic optimization models like two-stage stochastic programming or optimization under chance constraints are natural ideas to account for these challenges. On the down side, many of these approaches require distributional information, which is often not available in practice. Moreover, they are notoriously computationally expensive. Robust optimization models exclude distributional information from the actual optimization problem. Instead, a robust solution must be feasible under all scenarios of a carefully chosen scenario set. Typically, this leads to optimization problems that can be solved almost as quickly as the nominal problem. Another advantage of robust optimization models are the hard guarantees the solutions fulfill by design. Finally, one can use even very basic distributional information to give further, stochastic guarantees for the feasibility of the solutions.

While robust optimization quickly became a success story for convex, single stage optimization problems it has been observed early on, that two-stage robust optimization is desirable for many applications. Typically, graph based problems require two-stage robust models for practical relevance. For a long time two-stage robust optimization has been considered rather wishful thinking than applicable method. But, today strong theoretical results and techniques have been developed that make it a very useful method. Nevertheless, two-stage robust models in particular for combinatorial problems still pose algorithmic challenges.

A robust solution is not only designed with respect to a single data point but equally to a usually infinite set of variations of this data. The success of machine learning in recent years has drawn new attention to the question of how reliable such statistical results are for different applications. For example, small, irrelevant changes in data should not change the classification. A road sign should not be misread because of small changes that are almost invisible to a human. Moreover, there is growing awareness that biases included in training data can have grave adverse effects for the application of machine learning. It has been shown that robust optimization can be a remedy for such problems.

Show more
Show less

Aurélie C. Thiele, Southern Methodist University

Robust optimization with societal applications 

Abstract: I will present both strategic and tactical decision making models under high uncertainty with a focus on the sequential optimization problems that arise in societal applications such as wildfire management. 2018 was the costliest wildfire season on record in the United States, with 2017 being the second costliest, which suggests the need for novel, more effective models of resource allocation. The uncertainty is on fire occurrence and fire growth characteristics, which depend on exogenous resources such as weather conditions as well as exogenous resources used to mitigate or suppress the fire. Strategic decisions include resource allocation and deployment and location set covering problems.  Tactical decisions include resource re-allocation due to fluctuating fire load from initial attach dispatching to extended attack management. We will show how adaptive and adjustable robust optimization models can provide insightful solutions in problem settings that are difficult to solve with the traditional method of stochastic programming. The robust solutions perform well in simulations and are easy to explain to firefighting personnel. Time permitting we will discuss the extent of which this framework can be extended to health epidemics.   

Wolfram Wiesemann, Imperial College London

Optimal Hospital Care Scheduling During the SARS-CoV-2 Pandemic

Abstract: The COVID-19 pandemic has seen dramatic demand surges for hospital care that have placed a severe strain on health systems worldwide. As a result, policy makers are faced with the challenge of managing scarce hospital capacity so as to reduce the backlog of non-COVID patients whilst maintaining the ability to respond to any potential future increases in demand for COVID care. In this talk, we propose a nation-wide prioritization scheme that models each individual patient as a dynamic program whose states encode the patient’s health and treatment condition, whose actions describe the available treatment options, whose transition probabilities characterize the stochastic evolution of the patient’s health and whose rewards encode the contribution to the overall objectives of the health system. The individual patients’ dynamic programs are coupled through constraints on the available resources, such as hospital beds, doctors and nurses. We show that near-optimal solutions to the emerging weakly coupled counting dynamic program can be found through a fluid approximation that gives rise to a linear program whose size grows gracefully in the problem dimensions. Our case study for the National Health Service in England shows how years of life can be gained and costs reduced by prioritizing specific disease types over COVID patients, such as injury & poisoning, diseases of the respiratory system, diseases of the circulatory system, diseases of the digestive system and cancer.