• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

Gabrel, Virginie; Murat, Cécile; Wu, Lei (2010), Application d’un nouveau critère de robustesse pour le problème du plus court chemin. https://basepub.dauphine.fr/handle/123456789/5252

View/Open
gabrel_wu.PDF (387.7Kb)
Type
Document de travail / Working paper
Date
2010
Publisher
Université Paris-Dauphine
Series title
Note de recherche du LAMSADE
Series number
48
Published in
Paris
Pages
61
Metadata
Show full item record
Author(s)
Gabrel, Virginie
Murat, Cécile
Wu, Lei
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.
Subjects / Keywords
robustness analysis; shortest path problem; worst case criterion; maximum regret; integer linear programming

Related items

Showing items related by title and author.

  • Thumbnail
    La bw-robustesse pour le problème du plus court chemin 
    Wu, Lei; Gabrel, Virginie; Murat, Cécile (2011) Communication / Conférence
  • Thumbnail
    New models for the robust shortest path problem: complexity, resolution and generalization 
    Gabrel, Virginie; Murat, Cécile; Wu, Lei (2013) Article accepté pour publication ou publié
  • Thumbnail
    Plus courts chemins robustes 
    Gabrel, Virginie; Murat, Cécile (2007) Chapitre d'ouvrage
  • Thumbnail
    La pw‐robustesse : pourquoi un nouveau critère de robustesse et comment l’appliquer ? 
    Gabrel, Virginie; Murat, Cécile; Thièle, Aurélie (2013) Communication / Conférence
  • Thumbnail
    Recourse problem of the 2-stage robust location transportation problem 
    Remli, Nabila; Murat, Cécile; Gabrel, Virginie; Lacroix, Mathieu (2010) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo