Homepage
Previous JFRO
Organizing committee
Contact
36th Ile-de-France Operation Research Day
Robustesse
Date
This day took place
Wednesday, the 31 May 2017
Place
Conservatoire National des Arts et Métiers - (Amphi Robert Faure accès 1, étage -1, amphi Z) 292, rue Saint-Martin, 75003 Paris
How to get there?

Program of the day


09h30-10h00
Accueil

10h00-12h00
Une introduction à l'optimisation robuste combinatoire statique et ajustable
Mickael Poss (LIRMM)
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.

12h00-14h00
Déjeuner

14h00-14h40
Robust capacity expansion of a network under demand uncertainty: a bi-objective approach
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.

14h40-15h20
Optimisation robuste pour la localisation de nouveaux logements
Laurent Alfandari (ESSEC Business School - LIPN) and Juan-Carlos Espinoza
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.

15h20-15h40
Pause

15h40-16h20
Formulations for designing robust networks. An application to wind power collection.
Thomas Ridremont (CEDRIC (CNAM) - UMA (ENSTA))
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.

Choose language : Français English