Show simple item record

dc.contributor.authorGabrel, Virginie
dc.contributor.authorMurat, Cécile
dc.contributor.authorWu, Lei
dc.date.accessioned2010-12-07T15:26:04Z
dc.date.available2010-12-07T15:26:04Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5252
dc.description.abstractfrEn 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.en
dc.language.isofren
dc.subjectrobustness analysisen
dc.subjectshortest path problemen
dc.subjectworst case criterionen
dc.subjectmaximum regreten
dc.subjectinteger linear programmingen
dc.subject.ddc005en
dc.titleApplication d’un nouveau critère de robustesse pour le problème du plus court cheminen
dc.typeDocument de travail / Working paper
dc.description.abstractenIn 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.en
dc.publisher.nameUniversité Paris-Dauphineen
dc.publisher.cityParisen
dc.identifier.citationpages61en
dc.relation.ispartofseriestitleNote de recherche du LAMSADEen
dc.relation.ispartofseriesnumber48en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record