Abstract : Robust optimization (RO) has become a central framework to handle the uncertainty that arises in the parameters of optimization problems. While classical RO results can efficiently handle linear programs for a large variety of uncertainty sets, the situation is more complex for optimization problems involving discrete decisions. Efficient exact or approximate solution algorithms for such problems must exploit the combinatorial structure of the problems at hand. In this tutorial, we shall review key results of this field, which has witnessed a revival in the last ten years since the introduction of structured uncertainty sets (budget, ellipsoids, ...). We will show how the static robust counterparts of many polynomially solvable problems remain po lynomially solvable, and highlight problems that turn NP-hard. In a second part, we will address the field of adjustable robust optimization. We will introduce the classical techniques, based either on decomposition algorithms or decision rules. We shall also review shortly the very recent propositions to address multi-stage counterparts where some discrete optimization variables can be adapted to the values taken by the uncertain parameters.

Abstract : This talk deals with the problem of capacity expansion of a network under independent uncertain demands defined by interval sets. In this context, decisions about capacity expansion must be made before the demands are revealed. Standard robust models require the definition of an uncertainty domain and look for the minimum cost solution able to satisfy any demand within this domain. We propose, justify, and illustrate an alternative robust model based on a bi-objective formulation. Therefore, in addition to the cost criterion, we consider a second criterion, related to the Quality of Service, which measures the ability of a solution to handle any demand. The decision-maker can be interested in efficient solutions offering a compromise between these criteria. We study the complexity of the enumeration of the corresponding non-dominated set, and propose exact and approximation algorithms.

Abstract : On étudie le problème de sélectionner un sous-ensemble de villes pour y construire de nouveaux programmes immobiliers. L'objectif est de maximiser la satisfaction des acheteurs potentiels. L'allocation des demandes aux programmes sélectionnés est faite par un modèle de choix de type Multinomial-Logit, basé sur la distance, le prix de l'immobilier et le revenu. Deux modèles de robustesse sont proposés: dans le premier, l'incertitude porte sur les demandes des clients. Dans le second, on combine une ensemble discret de scénarios sur les utilités des clients (nominal, centré sur le prix ou centré sur la distance), et une approche de type Gamma-robustesse qui limite le nombre de sources de demande pouvant dévier de leur utilité nominale. La solution robuste doit rester réalisable pour la contrainte de budget. On montre que le sous-problème de recherche de la pire variation des paramètres reste dualisable malgré la structure discrète des scénarios, et conduit à une formulation linéaire du problème robuste. Des expériences numériques sur la région Parisienne montrent que la perte de valeur de la solution robuste est relativement faible comparée à la solution optimale des instances déviées.

Abstract : We are interested in the design of survivable capacitated rooted Steiner networks. Given a graph $G=(V,E)$, capacity and cost functions on $E$, a root $r$, a subset $T$ of $V$ of terminals and an integer $k$, we search for a minimum cost subset $E'subset E$, covering $T$ and $r$, such that the network induced by $E'$ is $(k+1)$-survivable: after the removal of any $k$ edges, there still exists a feasible flow from $r$ to $T$. We also consider the possibility of protecting a given number of edges. We propose three different formulations: a cut-set, a flow and a bi-level formulation where the second-level is a min-max problem (with an attacker and a defender). We propose algorithms for each problem formulation and compare their efficiency.