Minmax regret combinatorial optimization problems: an Algorithmic Perspective
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 2, pp. 101-129.

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.

DOI : https://doi.org/10.1051/ro/2011111
Classification : 90C11,  90C27,  90C35
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},
     zbl = {1270.90053},
     mrnumber = {2855948},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2011111/}
}
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] H. Aissi, C. Bazgan and D. Vanderpooten, Complexity of the minmax and minmax regret assignment problem. Oper. Res. Lett. 33 (2005) 634-640. | MR 2165144 | Zbl 1141.90457

[2] H. Aissi, C. Bazgan and D. Vanderpooten, Approximation of min-max and min-max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. 179 (2007) 281-290. | MR 2278627 | Zbl 1180.90359

[3] H. Aissi, C. Bazgan and D. Vanderpooten, Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. Lect. Notes Comput. Sci. 3669 (2005) 862-873. | MR 2257994 | Zbl 1142.68608

[4] H. Aissi, C. Bazgan and D. Vanderpooten, Min-max and min-max regret versions of some combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197 (2009) 427-438. | MR 2509273 | Zbl 1159.90472

[5] M.A. Aloulou, R. Kalai and D. Vanderpooten, 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] E. Alvarez-Miranda and A. Candia-Vejar, Robust Shortest Path: Models, Algorithms and Comparisons, Proceedings of the VI ALIO/EURO Workshop on Applied Combinatorial Optimization. Buenos Aires, Argentina (2008).

[7] I. Aron and P. Van Hentenryck, 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] I. Aron and P. Van Hentenryck, On the complexity of the robust spanning tree problem with interval data, Oper. Res. Lett. 32 (2004) 36-40. | MR 2017106 | Zbl 1056.90114

[9] T. Assavapokee, M.J. Realff and J.C. Ammons, Min-max Regret robust optimization approach on interval data uncertainty. J. Optim. Theory Appl. 137 (2008) 297-316. | MR 2395103 | Zbl 1151.90019

[10] I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. Ser. A 90 (2001) 263-272. | MR 1824074 | Zbl 0980.90070

[11] I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge lengths. Discr. App. Math. 127 (2003) 505-522. | MR 1976030 | Zbl 1038.90041

[12] I. Averbakh, Minmax regret linear resource allocation problems. Oper. Res. Lett. 32 (2004) 174-180. | MR 2017768 | Zbl 1137.90752

[13] I. Averbakh, Computing and minimizing the relative regret in combinatorial optimization with interval data. Discr. Optim. 2 (2005) 273-287. | MR 2184413 | Zbl 1172.90467

[14] I. Averbakh and S. Bereg, Facility location problems with uncertainty on the plane. Discret. Optim. 2 (2005) 3-34. | MR 2127326 | Zbl 1090.90128

[15] I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. ORSA J. Comput. 12 (2000) 104-110. | MR 1755973 | Zbl 1034.90007

[16] I. Averbakh and O. Berman, Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res. 123 (2000) 292-302. | MR 1803537 | Zbl 0967.90065

[17] I. Averbakh and V. Lebedev, Interval data regret network optimization problems. Discr. App. Math. 138 (2004) 289-301. | MR 2049651 | Zbl 1056.90010

[18] I. Averbakh and V. Lebedev, On the complexity of minmax regret linear programming. Eur. J. Oper. Res. 160 (2005) 227-231. | MR 2091170 | Zbl 1067.90132

[19] J.E. Beasley, OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990) 1069-1072.

[20] D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. Ser. B 98 (2003) 49-71. | MR 2019367 | Zbl 1082.90067

[21] D. Bertsimas and M. Sim, The price of robustness. Oper. Res. 52 (2004) 35-53. | MR 2066239 | Zbl 1165.90565

[22] L. Bianchi, M. Dorigo, L. Gambardella and W. Gutjahr, Metaheuristics in Stochastic Combinatorial Optimization: a Survey. IDSIA Technical Report, IDSIA-08-06 (2006), Natural Computing 8 (2009) 239-287. | MR 2505751 | Zbl 1162.90591

[23] R.E. Burkard and H. Dollani, A note on the robust 1-center problem on trees. Disc. Appl. Math. 138 (2004) 289-301. | Zbl 1013.90075

[24] A. Candia-Véjar and E. Álvarez-Miranda, On a class of interval data minmax regret CO problems. 2007 (2007) 123-128. | Zbl 1209.90298

[25] N. Chang and E. Davila, Siting and routing assessment for solid waste management under uncertainty using the grey min-max regret criterion. Environ. Manag. 38 (2006) 654-672.

[26] N. Chang and E. Davila, Minimax regret optimization analysis for a regional solid waste management system. Waste Manag. 27 (2007) 820-832.

[27] X. Chen, J. Hu and X. Hu, On the minimum risk-sum path problem, ESCAPE'07 Proceedings, Lect. Notes Comput. Sci. 4614 (2007) 175-185. | Zbl 1176.90601

[28] X. Chen, J. Hu and X. Hu, The minimum risk spanning tree problem, COCOA'07 Proceedings, Lecture Notes in Computer Science 4616 (2007) 81-90. | MR 2391852 | Zbl 1175.90057

[29] X. Chen, J. Hu and X. Hu, A new model for path planning with interval data. Comput. Oper. Res. 39 (2009) 1893-1899. | Zbl 1179.90319

[30] E. Conde, 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 2062932 | Zbl 1070.90129

[31] E. Conde, On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett. 33 (2005) 481-485. | MR 2146612 | Zbl 1195.90075

[32] E. Conde, Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res. 179 (2007) 1025-1039. | MR 2286526 | Zbl 1163.90384

[33] E. Conde, A branch and Bound algorithm for minimum spanning arborescences. J. Glob. Optim. 37 (2007) 467-480. | MR 2293666 | Zbl 1156.90027

[34] E. Conde, A note on the minmax regret centdian location on trees. Oper. Res. Lett. 36 (2008) 271-275. | MR 2396579 | Zbl 1144.90433

[35] E. Conde, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. Oper. Res. Lett. 38 (2010) 326-327. | MR 2647247 | Zbl 1197.90337

[36] E. Conde and A. Candia, Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res. 182 (2007) 561-577. | MR 2324548 | Zbl 1178.90053

[37] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solutions of a large scale traveling salesman problem. Oper. Res. 2 (1954) 393-410. | MR 70932 | Zbl 1187.90007

[38] V. Deineko and G. Woeginger, On the robust assigment problem under fixed number of cost scenarios. Oper. Res. Lett. 34 (2006) 175-179. | MR 2192375

[39] M. Demir, B. Tansel and G. Scheuenstuhl, Tree Network 1-median location with interval data: a parameter space-based approach. IIE Trans. 37 (2005) 429-439.

[40] R. Hites, Y. De Smeta, N. Risse, N. Salazar-Neumann and P. Vincke, About the applicability of MCDA to some robustness problems. Eur. J. Oper. Res. 174 (2006) 322-332. | Zbl 1116.90051

[41] O. Karasan, M. Pinar and H. Yaman, The Robust Shortest Path Problem with Interval Data. Technical Report Bilkent University (2001), revised (2004).

[42] A. Kasperski, Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Studies in Fuzzines and Soft Computing, Springer (2008). | MR 2451596 | Zbl 1154.90017

[43] A. Kasperski and P. Zieliński, An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97 (2006) 177-180. | MR 2195214 | Zbl 1184.68640

[44] A. Kasperski and P. Zieliński, The robust shortest path problem in series-parallel multidigraphs with interval data. Oper. Res. Lett. 34 (2006) 69-76. | MR 2186077 | Zbl 1080.90058

[45] A. Kasperski and P. Zieliński, On combinatorial optimization problems on matroids with uncertain weights. Eur. J. Oper. Res. 177 (2007) 851-864. | MR 2268912 | Zbl 1110.90075

[46] A. Kazakci, S. Rozakis and D. Vanderpooten, Energy crop supply in France: a min-max regret approach. J. Oper. Res. Soc. 58 (2007) 1470-1479. | Zbl 1143.90019

[47] P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers (1997). | MR 1480918 | Zbl 0873.90071

[48] R. Loulou and A. Kanudia, Minimax regret strategies for greenhouse gas abatement: methodology and application. Oper. Res. Lett. 25 (1999) 219-230. | Zbl 0972.91073

[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 1420865 | Zbl 0839.90135

[50] H.E. Mausser and M. Laguna, A new mixed integer formulation for the maximum regret problem. Int. Trans. Oper. Res. 5 (1998) 389-403.

[51] H.E. Mausser and M. Laguna, Minimising the maximum relative regret for linear programmes with interval objective function coefficents. J. Oper. Res. Soc. 50 (1999) 1063-1070. | Zbl 1054.90619

[52] H.E. Mausser and M. Laguna, A heuristic to minmimax absolute regret for linear programs with interval objective function. Eur. J. Oper. Res. 117 (1999) 157-174. | Zbl 0998.90058

[53] R. Montemanni, A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174 (2006) 1479-1490. | MR 2254322 | Zbl 1102.90050

[54] R. Montemanni, L.M. Gambardella and A.V. Donati, A branch and bound algorithm for the robust shortest path with interval data. Oper. Res. Lett. 32 (2004) 225-232. | MR 2028339 | Zbl 1045.90086

[55] R. Montemanni and L.M. Gambardella, An exact algorithm for the robust shortest path problem with interval data. Comput. Oper. Res. 31 (2004) 1667-1680. | MR 2046326 | Zbl 1073.90055

[56] R. Montemanni and L.M. Gambardella, A branch and bound algorithm for the robust spanning tree with interval data. Eur. J. Oper. Res. 161 (2005) 771-779. | MR 2099234 | Zbl 1071.90047

[57] R. Montemanni and L.M. Gambardella, The robust shortest path problem with interval data via Benders decomposition, 40R 3 (2005) 315-328. | MR 2191379 | Zbl 1134.90538

[58] R. Montemanni, J. Barta and L.M. Gambardella, Heuristic and preprocessing techniques for the robust traveling salesman problem with interval data. Technical Report IDSIA-01-06 (2006).

[59] R. Montemanni, J. Barta and L.M. Gambardella, The robust traveling salesman problem with interval data. Transp. Sci. 41 (2007) 366-381.

[60] Y. Nikulin, Robustness in combinatorial optimization and scheduling theory: An annotated bibliography. Christian-Albrechts University in Kiel, Working paper (2005).

[61] Y. Nikulin, Simulated annealing algorithm for the robust spanning tree problem. J. Heurist. 14 (2008) 391-402. | Zbl 1152.90012

[62] Y. Nikulin, Solving the robust shortest path problem with interval data using probabilistic metaheuristic approach. N597 CAU (2005) (with A. Drexl).

[63] J. Pereira and I. Averbakh, Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38 (2011) 1153-1163 | MR 2749473 | Zbl 1208.90107

[64] M. Salazar-Neumann, The robust minimum spanning tree problem: Compact and convex uncertainty. Oper. Res. Lett. 35 (2007) 17-22. | MR 2294677 | Zbl 1278.90418

[65] L.V. Snyder, Facility location under uncertainty: A review. IIE Trans. 38 (2006) 547-564.

[66] H. Yaman, O. Karasan and M. Pinar, The robust spanning tree with interval data. Oper. Res. Lett. 29 (2001) 31-40. | MR 1847924 | Zbl 0981.05029

[67] P. Zieliński, The computational complexity of the relative robust shortest path problem with interval data. Eur. J. Oper. Res. 158 (2004) 570-576. | MR 2068094 | Zbl 1056.90125