Date
2010
Ville de l'éditeur
Paris
Nom de l'éditeur
Université Paris-Dauphine
Titre de la collection
Note de recherche du LAMSADE
n° dans la collection
48
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
robustness analysis; shortest path problem; worst case criterion; maximum regret; integer linear programming
Auteur
Gabrel, Virginie
Murat, Cécile
Wu, Lei
Type
Document de travail / Working paper
Nombre de pages du document
61
Résumé en français
En optimisation, les sources d’incertitude et d’imprécision sont nombreuses et rendent souvent
difficiles l’affectation d’une unique valeur plausible à chacun des paramètres du modèle. Il peut alors
être plus pertinent de retenir un ensemble de valeurs possibles pour chacun des paramètres. Un scénario est défini en choisissant une unique valeur dans chacun des ensembles. Dans ce contexte, une
solution robuste doit être aussi bonne que possible dans une grande majorité de scénarios et jamais
trop mauvaise. Cette caractérisation donne lieu à de nombreuses interprétations possibles qui justifient différentes approches de la robustesse. Ces approches se distinguent par les différents modèles
utilisés pour représenter les facteurs d’incertitude, par les méthodologies utilisées pour mesurer la
robustesse, et finalement par la conception et l’analyse des méthodes de résolution. Dans ce papier, nous nous focalisons sur l’application de nouveaux critères pour le plus court chemin avec
des valeurs incertaines sur les arcs. Nous commençons par rappeler deux modèles d’incertitude
habituellement considérés : le modèle par intervalle et le modèle par ensemble discret de scénarios.
Pour chacun d’entre eux, nous appliquons les nouveaux critères de robustesse appelés bw-robustesse
et bw-déviation (proposés initialement par B. Roy) qui généralisent respectivement les critères du pire cas et du regret maximum. Dans chacun des cas, nous avons à résoudre des programmes linéaires
en nombres entiers de très grandes tailles. Nos expérimentations numériques sur des graphes de
grandes tailles montrent qu’un solveur standard de type Cplex est capable de résoudre ces nouveaux
problèmes, ce qui est très prometteur du point de vue de l’analyse de robustesse.
Résumé en anglais
In optimization, it is used to deal with uncertain and unaccurate factors which make difficult the
assignment of a single value to each model parameters. It may be more relevant to assign a set of
values to each uncertain model parameters. A scenario is defined by choosing one value in each
uncertainty set. In this context, a robust solution has to be as good as possible under a majority of
scenarios and never be too bad. This characterization leaves place to many possible interpretations
and therefore gives rise to various approaches of robustness. These approaches differ from models
used to represent uncertain factors, from methodology used to measure robustness, and finally from
analysis and design of resolution methods. In this paper, we focus on the application of new criteria
for the shortest path problem with uncertain arc lengths. At first, we present two uncertainty models
usually considered : the interval model and the discrete scenario set model. For each model, we
apply new criteria of robustness, called bw-robustness and bw-deviation (originally proposed by B.
Roy) which respectively generalize the worst case criterion and the maximum regret criterion. In
each case, we have to solve large scale integer linear programs. Our computational experiments on
large scale graphs show that a standard solver like Cplex is able to solve these new problems which
are very promising for robustness analysis.
