• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Application d’un nouveau critère de robustesse pour le problème du plus court chemin

Thumbnail
View/Open
gabrel_wu.PDF (387.7Kb)
Date
2010
Publisher city
Paris
Publisher
Université Paris-Dauphine
Collection title
Note de recherche du LAMSADE
Collection Id
48
Dewey
Programmation, logiciels, organisation des données
Sujet
robustness analysis; shortest path problem; worst case criterion; maximum regret; integer linear programming
URI
https://basepub.dauphine.fr/handle/123456789/5252
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Gabrel, Virginie
Murat, Cécile
Wu, Lei
Type
Document de travail / Working paper
Item number of pages
61
Abstract (FR)
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.
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.