# Minmax regret combinatorial optimization problems: an Algorithmic Perspective

Alfredo Candia-Véjar; Eduardo Álvarez-Miranda; Nelson Maculan

RAIRO - Operations Research (2011)

- Volume: 45, Issue: 2, page 101-129
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topCandia-Véjar, Alfredo, Álvarez-Miranda, Eduardo, and Maculan, Nelson. "Minmax regret combinatorial optimization problems: an Algorithmic Perspective." RAIRO - Operations Research 45.2 (2011): 101-129. <http://eudml.org/doc/276359>.

@article{Candia2011,

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.
},

author = {Candia-Véjar, Alfredo, Álvarez-Miranda, Eduardo, Maculan, Nelson},

journal = {RAIRO - Operations Research},

keywords = {Minmax regret model; combinatorial optimization;
exact algorithms and heuristics; robust optimization.; minmax regret model; exact algorithms and heuristics; robust optimization},

language = {eng},

month = {8},

number = {2},

pages = {101-129},

publisher = {EDP Sciences},

title = {Minmax regret combinatorial optimization problems: an Algorithmic Perspective},

url = {http://eudml.org/doc/276359},

volume = {45},

year = {2011},

}

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

DA - 2011/8//

PB - EDP Sciences

VL - 45

IS - 2

SP - 101

EP - 129

AB -
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.

LA - eng

KW - Minmax regret model; combinatorial optimization;
exact algorithms and heuristics; robust optimization.; minmax regret model; exact algorithms and heuristics; robust optimization

UR - http://eudml.org/doc/276359

ER -

## References

top- H. Aissi, C. Bazgan and D. Vanderpooten, Complexity of the minmax and minmax regret assignment problem. Oper. Res. Lett.33 (2005) 634–640. Zbl1141.90457
- 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. Zbl1180.90359
- 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. Zbl1142.68608
- 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. Zbl1159.90472
- 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).
- 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).
- 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.
- 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. Zbl1056.90114
- 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. Zbl1151.90019
- I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. Ser. A90 (2001) 263–272. Zbl0980.90070
- I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge lengths. Discr. App. Math.127 (2003) 505–522. Zbl1038.90041
- I. Averbakh, Minmax regret linear resource allocation problems. Oper. Res. Lett.32 (2004) 174–180. Zbl1137.90752
- I. Averbakh, Computing and minimizing the relative regret in combinatorial optimization with interval data. Discr. Optim.2 (2005) 273–287. Zbl1172.90467
- I. Averbakh and S. Bereg, Facility location problems with uncertainty on the plane. Discret. Optim.2 (2005) 3–34. Zbl1090.90128
- I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. ORSA J. Comput.12 (2000) 104–110. Zbl1034.90007
- I. Averbakh and O. Berman, Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res.123 (2000) 292–302. Zbl0967.90065
- I. Averbakh and V. Lebedev, Interval data regret network optimization problems. Discr. App. Math.138 (2004) 289–301. Zbl1056.90010
- I. Averbakh and V. Lebedev, On the complexity of minmax regret linear programming. Eur. J. Oper. Res.160 (2005) 227–231. Zbl1067.90132
- J.E. Beasley, OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc.41 (1990) 1069–1072.
- D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program. Ser. B98 (2003) 49–71. Zbl1082.90067
- D. Bertsimas and M. Sim, The price of robustness. Oper. Res.52 (2004) 35–53. Zbl1165.90565
- L. Bianchi, M. Dorigo, L. Gambardella and W. Gutjahr, Metaheuristics in Stochastic Combinatorial Optimization: a Survey. IDSIA Technical Report, IDSIA-08-06 (2006), Natural Computing8 (2009) 239–287. Zbl1162.90591
- R.E. Burkard and H. Dollani, A note on the robust 1-center problem on trees. Disc. Appl. Math.138 (2004) 289–301. Zbl1013.90075
- A. Candia-Véjar and E. Álvarez-Miranda, On a class of interval data minmax regret CO problems. 2007 (2007) 123–128. Zbl1209.90298
- 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.
- N. Chang and E. Davila, Minimax regret optimization analysis for a regional solid waste management system. Waste Manag.27 (2007) 820–832.
- 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. Zbl1176.90601
- X. Chen, J. Hu and X. Hu, The minimum risk spanning tree problem, COCOA'07 Proceedings, Lecture Notes in Computer Science4616 (2007) 81–90. Zbl1175.90057
- X. Chen, J. Hu and X. Hu, A new model for path planning with interval data. Comput. Oper. Res.39 (2009) 1893–1899. Zbl1179.90319
- E. Conde, An improved algorithm for selecting p items with uncertain return according to the minmax-regret criterion. Math. Program. Ser. A100 (2001) 345–353. Zbl1070.90129
- E. Conde, On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett.33 (2005) 481–485. Zbl1195.90075
- E. Conde, Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res.179 (2007) 1025–1039. Zbl1163.90384
- E. Conde, A branch and Bound algorithm for minimum spanning arborescences. J. Glob. Optim.37 (2007) 467–480. Zbl1156.90027
- E. Conde, A note on the minmax regret centdian location on trees. Oper. Res. Lett.36 (2008) 271–275. Zbl1144.90433
- E. Conde, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. Oper. Res. Lett.38 (2010) 326–327. Zbl1197.90337
- E. Conde and A. Candia, Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res.182 (2007) 561–577. Zbl1178.90053
- G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, Solutions of a large scale traveling salesman problem. Oper. Res.2 (1954) 393–410.
- V. Deineko and G. Woeginger, On the robust assigment problem under fixed number of cost scenarios. Oper. Res. Lett.34 (2006) 175–179.
- 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.
- 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. Zbl1116.90051
- O. Karasan, M. Pinar and H. Yaman, The Robust Shortest Path Problem with Interval Data. Technical Report Bilkent University (2001), revised (2004). Zbl0981.05029
- A. Kasperski, Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Studies in Fuzzines and Soft Computing, Springer (2008). Zbl1154.90017
- A. Kasperski and P. Zieliński, An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett.97 (2006) 177–180. Zbl1184.68640
- 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. Zbl1080.90058
- A. Kasperski and P. Zieliński, On combinatorial optimization problems on matroids with uncertain weights. Eur. J. Oper. Res.177 (2007) 851–864. Zbl1110.90075
- 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. Zbl1143.90019
- P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers (1997). Zbl0873.90071
- R. Loulou and A. Kanudia, Minimax regret strategies for greenhouse gas abatement: methodology and application. Oper. Res. Lett.25 (1999) 219–230. Zbl0972.91073
- T.L. Magnanti and L. Wolsey, optimal trees, network models, in Handbook in Operations research and management science7, edited by M.O. Ball et al., North-Holland, Amsterdam (1997) 503–615.
- H.E. Mausser and M. Laguna, A new mixed integer formulation for the maximum regret problem. Int. Trans. Oper. Res.5 (1998) 389–403.
- 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. Zbl1054.90619
- 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. Zbl0998.90058
- R. Montemanni, A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res.174 (2006) 1479–1490. Zbl1102.90050
- 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. Zbl1045.90086
- 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. Zbl1073.90055
- 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. Zbl1071.90047
- R. Montemanni and L.M. Gambardella, The robust shortest path problem with interval data via Benders decomposition, 40R3 (2005) 315–328. Zbl1134.90538
- 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).
- R. Montemanni, J. Barta and L.M. Gambardella, The robust traveling salesman problem with interval data. Transp. Sci.41 (2007) 366–381.
- Y. Nikulin, Robustness in combinatorial optimization and scheduling theory: An annotated bibliography. Christian-Albrechts University in Kiel, Working paper (2005).
- Y. Nikulin, Simulated annealing algorithm for the robust spanning tree problem. J. Heurist.14 (2008) 391–402. Zbl1152.90012
- Y. Nikulin, Solving the robust shortest path problem with interval data using probabilistic metaheuristic approach. N597 CAU (2005) (with A. Drexl).
- J. Pereira and I. Averbakh, Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res.38 (2011) 1153–1163 Zbl1208.90107
- M. Salazar-Neumann, The robust minimum spanning tree problem: Compact and convex uncertainty. Oper. Res. Lett.35 (2007) 17–22. Zbl1278.90418
- L.V. Snyder, Facility location under uncertainty: A review. IIE Trans.38 (2006) 547–564.
- H. Yaman, O. Karasan and M. Pinar, The robust spanning tree with interval data. Oper. Res. Lett.29 (2001) 31–40. Zbl0981.05029
- P. Zieliński, The computational complexity of the relative robust shortest path problem with interval data. Eur. J. Oper. Res.158 (2004) 570–576. Zbl1056.90125

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.