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

Abstract

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

How to cite

top

Candia-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
  1. 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
  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.  Zbl1180.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.  Zbl1142.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.  Zbl1159.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.  Zbl1056.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.  Zbl1151.90019
  10. I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. Ser. A90 (2001) 263–272.  Zbl0980.90070
  11. I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge lengths. Discr. App. Math.127 (2003) 505–522.  Zbl1038.90041
  12. I. Averbakh, Minmax regret linear resource allocation problems. Oper. Res. Lett.32 (2004) 174–180.  Zbl1137.90752
  13. I. Averbakh, Computing and minimizing the relative regret in combinatorial optimization with interval data. Discr. Optim.2 (2005) 273–287.  Zbl1172.90467
  14. I. Averbakh and S. Bereg, Facility location problems with uncertainty on the plane. Discret. Optim.2 (2005) 3–34.  Zbl1090.90128
  15. I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. ORSA J. Comput.12 (2000) 104–110.  Zbl1034.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.  Zbl0967.90065
  17. I. Averbakh and V. Lebedev, Interval data regret network optimization problems. Discr. App. Math.138 (2004) 289–301.  Zbl1056.90010
  18. I. Averbakh and V. Lebedev, On the complexity of minmax regret linear programming. Eur. J. Oper. Res.160 (2005) 227–231.  Zbl1067.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. B98 (2003) 49–71.  Zbl1082.90067
  21. D. Bertsimas and M. Sim, The price of robustness. Oper. Res.52 (2004) 35–53.  Zbl1165.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 Computing8 (2009) 239–287.  Zbl1162.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.  Zbl1013.90075
  24. A. Candia-Véjar and E. Álvarez-Miranda, On a class of interval data minmax regret CO problems. 2007 (2007) 123–128.  Zbl1209.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.  Zbl1176.90601
  28. 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
  29. 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
  30. 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
  31. E. Conde, On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett.33 (2005) 481–485.  Zbl1195.90075
  32. E. Conde, Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res.179 (2007) 1025–1039.  Zbl1163.90384
  33. E. Conde, A branch and Bound algorithm for minimum spanning arborescences. J. Glob. Optim.37 (2007) 467–480.  Zbl1156.90027
  34. E. Conde, A note on the minmax regret centdian location on trees. Oper. Res. Lett.36 (2008) 271–275.  Zbl1144.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.  Zbl1197.90337
  36. E. Conde and A. Candia, Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res.182 (2007) 561–577.  Zbl1178.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.  
  38. V. Deineko and G. Woeginger, On the robust assigment problem under fixed number of cost scenarios. Oper. Res. Lett.34 (2006) 175–179.  
  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.  Zbl1116.90051
  41. O. Karasan, M. Pinar and H. Yaman, The Robust Shortest Path Problem with Interval Data. Technical Report Bilkent University (2001), revised (2004).  Zbl0981.05029
  42. A. Kasperski, Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Studies in Fuzzines and Soft Computing, Springer (2008).  Zbl1154.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.  Zbl1184.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.  Zbl1080.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.  Zbl1110.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.  Zbl1143.90019
  47. P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers (1997).  Zbl0873.90071
  48. R. Loulou and A. Kanudia, Minimax regret strategies for greenhouse gas abatement: methodology and application. Oper. Res. Lett.25 (1999) 219–230.  Zbl0972.91073
  49. 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.  
  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.  Zbl1054.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.  Zbl0998.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.  Zbl1102.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.  Zbl1045.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.  Zbl1073.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.  Zbl1071.90047
  57. R. Montemanni and L.M. Gambardella, The robust shortest path problem with interval data via Benders decomposition, 40R3 (2005) 315–328.  Zbl1134.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.  Zbl1152.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 Zbl1208.90107
  64. M. Salazar-Neumann, The robust minimum spanning tree problem: Compact and convex uncertainty. Oper. Res. Lett.35 (2007) 17–22.  Zbl1278.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.  Zbl0981.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.  Zbl1056.90125

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.