Combinatorial Optimization under uncertainty through robustness

Joint seminar of the GdT DOR and POC

3rd October 2024

2 rue Conté

At the CNAM
Amphitheater Gaston Planté (access 35, 1st floor)

See the list of the participants here

9h00 - 9h30  Welcome

9h30 - 11h00  Christina Büsing: Solving Robust Binary Optimization Problem with Budget Uncertainty

Robust optimization with budgeted uncertainty, as proposed by Bertsimas and Sim in the early 2000s, is one of the most popular approaches for integrating uncertainty in optimization problems. The existence of a compact reformulation for MILPs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is actually quite poor due to its weak linear relaxation.

To overcome this weakness, we propose a bilinear formulation for robust binary programming, which is as strong as theoretically possible. From this bilinear formulation, we derive strong linear formulations as well as structural properties, which we use within a tailored branch and bound algorithm. Furthermore, we propose a procedure to derive new classes of valid inequalities for robust binary optimization problems. For this, we recycle valid inequalities of the underlying non-robust problem such that the additional variables from the robust formulation are incorporated. The valid inequalities to be recycled may either be readily available model-constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems.

11h00 - 11h30  Coffee break

11h30 - 12h15  Matteo Petris: Robust approaches for the Kidney Exchange Problem

In the Kidney Exchange Problem (KEP), we consider a pool of altruistic donors and incompatible patient-donor pairs. Kidney exchanges can be modelled in a directed weighted graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor. The weights on the arcs represent the medical benefit which measures the quality of the associated transplantation. For medical reasons, circuits and paths are of limited length and are associated with a medical benefit to perform the transplants. The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality (all weights equal to one). In this work, we consider two types of uncertainty in the KEP which stem from the estimation of the medical benefit (weights of the arcs) and from the failure of a transplantation (existence of the arcs). Both uncertainty are modelled via uncertainty sets  with constant budget.
The robust approach entails finding the best KEP solution in the worst-case scenario within the uncertainty set. We modelled the robust counter-part by means of a max-min formulation which is defined on exponentially-many variables associated with the circuits and paths. We propose different exact approaches to solve it: either based on the result of Bertsimas and Sim or on a reformulation to a single-level problem.
In both cases, the core algorithm is based on a Branch-Price-and-Cut approach where the exponentially-many variables are dynamically generated. The computational experiments prove the efficiency of our approach. 

12h15 - 14h00 Lunch

14h00 - 14h45  Henri Lefebvre: Advances in Two-Stage Robust Optimization: An Augmented Lagrangian Duality Viewpoint

Two-stage robust optimization problems with integer recourse decisions are notoriously challenging. While traditional duality approaches are effective in the convex case, they fail to be applicable due to the presence of integer variables. Nevertheless, over the last decade, significant advances have been made in developing exact algorithms for integer-constrained problems. In this talk, we examine these recent developments through the lens of augmented Lagrangian duality. We begin with an introduction to augmented Lagrangian duality theory in the mixed-integer setting. Then, we dive into recent results from the two-stage robust optimization literature — namely the works of Arslan et al. (2021), Detienne et al. (2024), Subramanyam (2022), Lefebvre et al. (2024a–b) — and show how these results can be effectively derived using the augmented Lagrangian duality framework. This talk aims at demonstrating the power and effectiveness of augmented Lagrangian duality in tackling two-stage robust optimization problems and to motivate research in that direction. The discussion is based on  a joint work with Martin Schmidt. 

14h45 - 15h30  Ayse Nur Arslan: Uncertainty reduction in robust optimization

Uncertainty reduction has recently been introduced in the robust optimization literature as a relevant special case of decision-dependent uncertainty. Herein, we identify two relevant situations in which the problem is polynomially solvable.
We further provide insights into possible MILP reformulations and the strength of their continuous relaxations. 

15h30 - 16h00 Coffee break

16h00 - 16h45  Michael Poss: Polyhedral robust optimization and decision-dependent information discovery

This talk will first cover well-known complexity results in robust combinatorial optimization with polyhedral uncertainty. In particular, we will explain that the main computational difficulty of the problem arises from a non-constant number of constraints (other than bounds) in the polyhedral description. We will then discuss the extension of these techniques to some non-linear binary problems and problems with constraint uncertainty. In the latter case, the Dantzig-Wolfe reformulation appears to be particularly efficient from the numerical viewpoint. Finally, we will turn to decision-dependent information discovery and show how these results can be applied to obtain a compact MILP reformulation for this case.

Organizers:

- Zacharie Ales

- Ivana Ljubic

- Michaël Poss