Volume 45, Number 2, April-June 2011
|Page(s)||101 - 129|
|Published online||24 August 2011|
Minmax regret combinatorial optimization problems: an Algorithmic Perspective
Modeling and Industrial Management Department, Universidad de Talca,
Curicó, Chile. firstname.lastname@example.org
2 Operations Management Master Program, Universidad de Talca, Curicó, Chile.
3 COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil.
Accepted: 19 May 2011
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.
Mathematics Subject Classification: 90C11 / 90C27 / 90C35
Key words: Minmax regret model / combinatorial optimization / exact algorithms and heuristics / robust optimization.
© EDP Sciences, ROADEF, SMAI, 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.