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.
Mots-clés : minmax regret model, combinatorial optimization, exact algorithms and heuristics, robust optimization
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2011111/
[1] , and , Complexity of the minmax and minmax regret assignment problem. Oper. Res. Lett. 33 (2005) 634-640. | MR | Zbl
[2] , and , Approximation of min-max and min-max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. 179 (2007) 281-290. | MR | Zbl
[3] , and , Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. Lect. Notes Comput. Sci. 3669 (2005) 862-873. | MR | Zbl
[4] , and , Min-max and min-max regret versions of some combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197 (2009) 427-438. | MR | Zbl
[5] , and , Minmax regret 1-center problem on a network with a discrete set of scenarios. Lamsade technical Report No. 132, LAMSADE, Université Paris-Dauphine, Cahier du LAMSADE (2006).
[6] and , Robust Shortest Path: Models, Algorithms and Comparisons, Proceedings of the VI ALIO/EURO Workshop on Applied Combinatorial Optimization. Buenos Aires, Argentina (2008).
[7] and , A constraint satisfaction approach to the robust spanning tree with interval data, Proceedings of the International Conference on Uncertainty in Artificial Intelligence UAI (2002) 18-25.
[8] and , On the complexity of the robust spanning tree problem with interval data, Oper. Res. Lett. 32 (2004) 36-40. | MR | Zbl
[9] , and , Min-max Regret robust optimization approach on interval data uncertainty. J. Optim. Theory Appl. 137 (2008) 297-316. | MR | Zbl
[10] , On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. Ser. A 90 (2001) 263-272. | MR | Zbl
[11] , Complexity of robust single facility location problems on networks with uncertain edge lengths. Discr. App. Math. 127 (2003) 505-522. | MR | Zbl
[12] , Minmax regret linear resource allocation problems. Oper. Res. Lett. 32 (2004) 174-180. | MR | Zbl
[13] , Computing and minimizing the relative regret in combinatorial optimization with interval data. Discr. Optim. 2 (2005) 273-287. | MR | Zbl
[14] and , Facility location problems with uncertainty on the plane. Discret. Optim. 2 (2005) 3-34. | MR | Zbl
[15] and , Minmax regret median location on a network under uncertainty. ORSA J. Comput. 12 (2000) 104-110. | MR | Zbl
[16] and , Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res. 123 (2000) 292-302. | MR | Zbl
[17] and , Interval data regret network optimization problems. Discr. App. Math. 138 (2004) 289-301. | MR | Zbl
[18] and , On the complexity of minmax regret linear programming. Eur. J. Oper. Res. 160 (2005) 227-231. | MR | Zbl
[19] , OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990) 1069-1072.
[20] and , Robust discrete optimization and network flows. Math. Program. Ser. B 98 (2003) 49-71. | MR | Zbl
[21] and , The price of robustness. Oper. Res. 52 (2004) 35-53. | MR | Zbl
[22] , , and , Metaheuristics in Stochastic Combinatorial Optimization: a Survey. IDSIA Technical Report, IDSIA-08-06 (2006), Natural Computing 8 (2009) 239-287. | MR | Zbl
[23] and , A note on the robust 1-center problem on trees. Disc. Appl. Math. 138 (2004) 289-301. | Zbl
[24] and , On a class of interval data minmax regret CO problems. 2007 (2007) 123-128. | Zbl
[25] and , Siting and routing assessment for solid waste management under uncertainty using the grey min-max regret criterion. Environ. Manag. 38 (2006) 654-672.
[26] and , Minimax regret optimization analysis for a regional solid waste management system. Waste Manag. 27 (2007) 820-832.
[27] , and , On the minimum risk-sum path problem, ESCAPE'07 Proceedings, Lect. Notes Comput. Sci. 4614 (2007) 175-185. | Zbl
[28] , and , The minimum risk spanning tree problem, COCOA'07 Proceedings, Lecture Notes in Computer Science 4616 (2007) 81-90. | MR | Zbl
[29] , and , A new model for path planning with interval data. Comput. Oper. Res. 39 (2009) 1893-1899. | Zbl
[30] , An improved algorithm for selecting p items with uncertain return according to the minmax-regret criterion. Math. Program. Ser. A 100 (2001) 345-353. | MR | Zbl
[31] , On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett. 33 (2005) 481-485. | MR | Zbl
[32] , Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res. 179 (2007) 1025-1039. | MR | Zbl
[33] , A branch and Bound algorithm for minimum spanning arborescences. J. Glob. Optim. 37 (2007) 467-480. | MR | Zbl
[34] , A note on the minmax regret centdian location on trees. Oper. Res. Lett. 36 (2008) 271-275. | MR | Zbl
[35] , A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. Oper. Res. Lett. 38 (2010) 326-327. | MR | Zbl
[36] and , Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res. 182 (2007) 561-577. | MR | Zbl
[37] , and , Solutions of a large scale traveling salesman problem. Oper. Res. 2 (1954) 393-410. | MR | Zbl
[38] and , On the robust assigment problem under fixed number of cost scenarios. Oper. Res. Lett. 34 (2006) 175-179. | MR
[39] , and , Tree Network 1-median location with interval data: a parameter space-based approach. IIE Trans. 37 (2005) 429-439.
[40] , , , and , About the applicability of MCDA to some robustness problems. Eur. J. Oper. Res. 174 (2006) 322-332. | Zbl
[41] , and , The Robust Shortest Path Problem with Interval Data. Technical Report Bilkent University (2001), revised (2004).
[42] , Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Studies in Fuzzines and Soft Computing, Springer (2008). | MR | Zbl
[43] and , An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97 (2006) 177-180. | MR | Zbl
[44] and , The robust shortest path problem in series-parallel multidigraphs with interval data. Oper. Res. Lett. 34 (2006) 69-76. | MR | Zbl
[45] and , On combinatorial optimization problems on matroids with uncertain weights. Eur. J. Oper. Res. 177 (2007) 851-864. | MR | Zbl
[46] , and , Energy crop supply in France: a min-max regret approach. J. Oper. Res. Soc. 58 (2007) 1470-1479. | Zbl
[47] and , Robust discrete optimization and its applications. Kluwer Academic Publishers (1997). | MR | Zbl
[48] and , Minimax regret strategies for greenhouse gas abatement: methodology and application. Oper. Res. Lett. 25 (1999) 219-230. | Zbl
[49] T.L. Magnanti and L. Wolsey, optimal trees, network models, in Handbook in Operations research and management science 7, edited by M.O. Ball et al., North-Holland, Amsterdam (1997) 503-615. | MR | Zbl
[50] and , A new mixed integer formulation for the maximum regret problem. Int. Trans. Oper. Res. 5 (1998) 389-403.
[51] and , Minimising the maximum relative regret for linear programmes with interval objective function coefficents. J. Oper. Res. Soc. 50 (1999) 1063-1070. | Zbl
[52] and , A heuristic to minmimax absolute regret for linear programs with interval objective function. Eur. J. Oper. Res. 117 (1999) 157-174. | Zbl
[53] , A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174 (2006) 1479-1490. | MR | Zbl
[54] , and , A branch and bound algorithm for the robust shortest path with interval data. Oper. Res. Lett. 32 (2004) 225-232. | MR | Zbl
[55] and , An exact algorithm for the robust shortest path problem with interval data. Comput. Oper. Res. 31 (2004) 1667-1680. | MR | Zbl
[56] and , A branch and bound algorithm for the robust spanning tree with interval data. Eur. J. Oper. Res. 161 (2005) 771-779. | MR | Zbl
[57] and , The robust shortest path problem with interval data via Benders decomposition, 40R 3 (2005) 315-328. | MR | Zbl
[58] , and , Heuristic and preprocessing techniques for the robust traveling salesman problem with interval data. Technical Report IDSIA-01-06 (2006).
[59] , and , The robust traveling salesman problem with interval data. Transp. Sci. 41 (2007) 366-381.
[60] , Robustness in combinatorial optimization and scheduling theory: An annotated bibliography. Christian-Albrechts University in Kiel, Working paper (2005).
[61] , Simulated annealing algorithm for the robust spanning tree problem. J. Heurist. 14 (2008) 391-402. | Zbl
[62] , Solving the robust shortest path problem with interval data using probabilistic metaheuristic approach. N597 CAU (2005) (with A. Drexl).
[63] and , Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38 (2011) 1153-1163 | MR | Zbl
[64] , The robust minimum spanning tree problem: Compact and convex uncertainty. Oper. Res. Lett. 35 (2007) 17-22. | MR | Zbl
[65] , Facility location under uncertainty: A review. IIE Trans. 38 (2006) 547-564.
[66] , and , The robust spanning tree with interval data. Oper. Res. Lett. 29 (2001) 31-40. | MR | Zbl
[67] , The computational complexity of the relative robust shortest path problem with interval data. Eur. J. Oper. Res. 158 (2004) 570-576. | MR | Zbl
Cité par Sources :
