Voir la notice de l'article provenant de la source Numdam
Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach, where uncertainty is modeled by assumed probability distributions over the space of all possible scenarios and the objective is to find a solution with good probabilistic performance. In the minmax regret (MMR) approach, the set of all possible scenarios is described deterministically, and the search is for a solution that performs reasonably well for all scenarios, i.e., that has the best worst-case performance. In this paper we discuss the computational complexity of some classic combinatorial optimization problems using MMR approach, analyze the design of several algorithms for these problems, suggest the study of some specific research problems in this attractive area, and also discuss some applications using this model.
@article{RO_2011__45_2_101_0,
author = {Candia-V\'ejar, Alfredo and \'Alvarez-Miranda, Eduardo and Maculan, Nelson},
title = {Minmax regret combinatorial optimization problems: an {Algorithmic} {Perspective}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {101--129},
publisher = {EDP-Sciences},
volume = {45},
number = {2},
year = {2011},
doi = {10.1051/ro/2011111},
mrnumber = {2855948},
zbl = {1270.90053},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2011111/}
}
TY - JOUR AU - Candia-Véjar, Alfredo AU - Álvarez-Miranda, Eduardo AU - Maculan, Nelson TI - Minmax regret combinatorial optimization problems: an Algorithmic Perspective JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2011 SP - 101 EP - 129 VL - 45 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2011111/ DO - 10.1051/ro/2011111 LA - en ID - RO_2011__45_2_101_0 ER -
%0 Journal Article %A Candia-Véjar, Alfredo %A Álvarez-Miranda, Eduardo %A Maculan, Nelson %T Minmax regret combinatorial optimization problems: an Algorithmic Perspective %J RAIRO - Operations Research - Recherche Opérationnelle %D 2011 %P 101-129 %V 45 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2011111/ %R 10.1051/ro/2011111 %G en %F RO_2011__45_2_101_0
Candia-Véjar, Alfredo; Álvarez-Miranda, Eduardo; Maculan, Nelson. Minmax regret combinatorial optimization problems: an Algorithmic Perspective. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 2, pp. 101-129. doi: 10.1051/ro/2011111
Cité par Sources :