Organized by Céline Gicquel and Vincent Leclère
Date: 19/11/2021 @ Ecole des Ponts
Registration
Free but compulsory : https://forms.gle/tXzyBGvHqh2UosBTA
Passe sanitaire obligatoire.
Planning
9:00 – 9:30 Optimization Problems in Graphs with Locational Uncertainty – Michael Poss, LIRMM, slides
9:30 – 10:00 Multipolar Robust Optimization – Walid Ben Ameur, Telecom SudParis, slides
10:00 – 10:30 Min-sup-min robust combinatorial optimization with few recourse solutions – Ayşe Nur Arslan, INSA Rennes, slides
10:30 – 11:00 A Finite epsilon-convergence Algorithm for 0-1 Mixed-Integer Convex Two-Stage Robust Problem – Boris Detienne, Université de Bordeaux, slides
11:00 – 11:30 Break
11:30 – 12:10 Monitoring with Limited Information – Dan Iancu, Standford and Insead, slides
12:10 – 12:50 Mathematical Foundations of Robust and Distributionally Robust Optimization – Daniel Kuhn, EPFL, Slides_1 Slides_2
12:50 – 13:30 Optimal Hospital Care Scheduling During the SARS-CoV-2 Pandemic – Wolfram Wiesemann, Imperial College, slides_1 slides_2
15:00 – 15:30 Risk-Averse Stochastic Programming and Distributionally Robust Optimization Via Operator Splitting – Welington de Oliveira, Ecole Nationale Supérieure des Mines de Paris, slides
15:30 – 16:00 Contextual chance-constrained and risk averse optimization – Bernardo Pagnoncelli, SKEMA, slides
16:00 – 16:30 Break
16:30 – 17:00 Robust Optimization Problems in Structural Mechanics – Jérémy Bleyer, ENPC, slides
17:00 – 17:30 Solution Robustness – Zacharie Alès, ENSTA, slides
The organizers acknowledge the support of axis DOR of GdR RO (CNRS), Air France and PGMO.
Abstracts
Optimization problems in graphs with locational uncertainty – Michael Poss
Many discrete optimization problems amount to select a feasible subgraph of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances in the chosen subgraph for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are NP-hard even when the feasible subgraphs consist either of all spanning trees or of all s-t paths. In view of this, we propose en exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be
solved efficiently. We also propose two types of polynomial-time approximation algorithms. The first one relies on solving a nominal counterpart of the problem considering pairwise worst-case distances. We study in details the resulting approximation ratio, which depends on the structure of the metric space and of the feasible subgraphs. The second algorithm considers the special case of s-t paths and leads to a fully-polynomial time approximation scheme. Our algorithms are numerically illustrated on a subway network design problem and a facility location problem.
joint work with Marin Bougeret and Jérémy Omer
Multipolar Robust Optimization – Walid Ben Ameur
We consider linear programs involving uncertain parameters and propose a new tractable robust counterpart which contains and generalizes several other models including the existing Affinely Adjustable Robust Counterpart and the Fully Adjustable Robust Counterpart. It consists in selecting a set of poles whose convex hull contains some projection of the uncertainty set, and computing a recourse strategy for each data scenario as a convex combination of some optimized recourses (one for each pole). We show that the proposed multipolar robust counterpart is tractable and its complexity is controllable. Further, we show that under some mild assumptions, two sequences of upper and lower bounds converge to the optimal value of the fully adjustable robust counterpart.
Min-sup-min robust combinatorial optimization with few recourse solutions – Arslan Ayse
In this talk, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective function and the constraints through functions that are not necessarily linear. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature.
A finite epsilon-convergence algorithm for 0-1 mixed-integer convex two-stage robust optimization with objective uncertainty – Boris Detienne
In this work, we study the class of optimization problems where some costs are not known at decision time and the decision flow is modeled as a two-stage process. We show how two-stage robust models for this class of problems can be solved by means of a branch-and-price algorithm where one may branch on continuous values so as to tighten the optimality gap. Our approach generalizes a recent result from the literature which addressed the linear case and was only applicable in presence of linking constraints involving binary variables, and extends the associated results to problems with convex constraints and general mixed-integer linking constraints. The convergence of the method is proven to epsilon-optimality.
Monitoring with Limited Information – Dan Iancu
We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which must be chosen in conjunction with a suitable stopping policy to maximize the reward. Such stopping problems arise in a variety of applications in healthcare, finance, and retailing, and often require excessive amounts of data for calibration purposes, and prohibitive computational resources to solve to optimality. To overcome these challenges, we propose a robust optimization approach, whereby adaptive uncertainty sets capture the information acquired through monitoring. We consider two versions of the problem—static and dynamic—depending on how the monitoring times are chosen. We show that under certain conditions, the same worst-case reward is achievable under either static or dynamic monitoring. This allows recovering the optimal dynamic monitoring policy by resolving static versions of the problem. We discuss cases when the static problem becomes tractable, and highlight conditions when monitoring at equi-distant times is optimal. Lastly, we showcase our framework in the context of a healthcare problem (monitoring heart transplant patients for Cardiac Allograft Vasculopathy), where we design optimal monitoring policies that substantially improve over the status quo treatment recommendations.
Mathematical Foundations of Robust and Distributionally Robust Optimization – Daniel Kuhn
Robust and distributionally robust optimization are modeling paradigms for decision-making under uncertainty where the uncertain parameters are only known to reside in an uncertainty set or are governed by any probability distribution from within an ambiguity set, respectively, and a decision is sought that minimizes a cost function under the most adverse outcome of the uncertainty. In this paper, we develop a rigorous and general theory of robust and distributionally robust nonlinear optimization using the language of convex analysis. Our framework is based on a generalized ‘primal-worst-equals-dual-best’ principle that establishes strong duality
between a semi-infinite primal worst and a non-convex dual best formulation, both of which admit finite convex reformulations. This principle offers an alternative formulation for robust optimization problems that may be computationally advantageous, and it obviates the need to mobilize the machinery of abstract semi-infinite duality theory to prove strong duality in distributionally robust optimization. We illustrate the modeling power of our approach through convex reformulations for distributionally robust optimization problems whose ambiguity sets are defined through general optimal transport distances, which generalize earlier results for Wasserstein ambiguity sets.
Optimal Hospital Care Scheduling During the SARS-CoV-2 Pandemic – Wolfram Wiesemann
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.
Robust optimization problems in structural mechanics – Jérémy Bleyer
This work explores the use of robust optimization formulations in the context of structural mechanics under material or loading uncertainties. We consider in particular limit analysis problems i.e. convex optimization problems looking for the maximal load a structure can sustain under equilibrium and strength condition constraints. We show that the arising uncertain convex inequalities are both convex in the decision variables and the uncertain parameters and discuss relevant approximate tractable reformulations. Finally, we evaluate the efficiency of linear decision rules on some illustrative examples.
This is a joint work with Vincent Leclère (CERMICS).
Risk-Averse Stochastic Programming and Distributionally Robust Optimization Via Operator Splitting – Welington de Oliveira
This work deals with a broad class of convex optimization problems under uncertainty. The approach is to pose the original problem as one of finding a zero of the sum of two appropriate monotone operators, which is solved by the celebrated Douglas-Rachford splitting method. The resulting algorithm, suitable for risk-averse stochastic programs and distributionally robust optimization with fixed support, separates the random cost mapping from the risk function composing the problem’s objective. Such a separation is exploited to compute iterates by alternating projections onto different convex sets. Scenario subproblems, free from the risk function and thus parallelizable, are projections onto the cost mappings’ epigraphs. The risk function is handled in an independent and dedicated step consisting of evaluating its proximal mapping that, in many important cases, amounts to projecting onto a certain ambiguity set. Variables get updated by straightforward projections on subspaces through independent computations for the various scenarios. The investigated approach enjoys significant flexibility and opens the way to handle, in a single algorithm, several classes of risk measures and ambiguity sets.
Contextual chance-constrained and risk averse optimization – Bernardo Pagnoncelli
Uncertainty in classical stochastic programming models is often described solely by independent random parameters, ignoring their dependence on multidimensional features. We propose a novel contextual chance-constrained programming formulation that incorporates features and argue that a solution that ignores them may not be implementable. We show the exponential convergence of our scheme as the number of data points increases. We illustrate our findings with a prescriptive portfolio problem that includes real-world features processed through Principal Feature Analysis.
This is joint work with H. Rahimian (Clemson University), Domingo Ramírez (PUC-Chile), Arturo Cifuentes (PUC-Chile).
Solution robustness – Zacharie Alès
Most robust optimization approaches focus on the quality robustness and only evaluate the relevance of their solutions through the objective function value of the nominal problem. However, it can be more important to optimize the solution robustness and, once the uncertainty is revealed, find an alternative feasible solution which is as similar as possible to the robust solution. This for example occurs when the robust solution is implemented on a regular basis or when the uncertainty is revealed late. We propose a framework which minimizes the solution robustness over a discrete set of scenarios while ensuring the optimality of the nominal objective. We study the complexity of several problems in this context. We highlight the benefits of solution robustness in a case study on a railroad planning problem in which we compare our approach to the anchored and the k-distance approaches.