Minmax regret combinatorial optimization problems: an Algorithmic Perspective
- 1 April 2011
- journal article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 45 (2) , 101-129
Abstract
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.Keywords
This publication has 54 references indexed in Scilit:
- Min–max and min–max regret versions of combinatorial optimization problems: A surveyEuropean Journal of Operational Research, 2009
- Min-Max Regret Robust Optimization Approach on Interval Data UncertaintyJournal of Optimization Theory and Applications, 2007
- Approximation of min–max and min–max regret versions of some combinatorial optimization problemsEuropean Journal of Operational Research, 2007
- Computing and minimizing the relative regret in combinatorial optimization with interval dataDiscrete Optimization, 2005
- Complexity of the min–max and min–max regret assignment problemsOperations Research Letters, 2005
- Facility location problems with uncertainty on the planeDiscrete Optimization, 2005
- Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and KnapsackLecture Notes in Computer Science, 2005
- Minmax regret linear resource allocation problemsOperations Research Letters, 2004
- Complexity of robust single facility location problems on networks with uncertain edge lengthsDiscrete Applied Mathematics, 2003
- On the complexity of a class of combinatorial optimization problems with uncertaintyMathematical Programming, 2001