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.  
  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.  
  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.  
  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.  
  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.  
  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.  
  10. I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. Ser. A90 (2001) 263–272.  
  11. I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge lengths. Discr. App. Math.127 (2003) 505–522.  
  12. I. Averbakh, Minmax regret linear resource allocation problems. Oper. Res. Lett.32 (2004) 174–180.  
  13. I. Averbakh, Computing and minimizing the relative regret in combinatorial optimization with interval data. Discr. Optim.2 (2005) 273–287.  
  14. I. Averbakh and S. Bereg, Facility location problems with uncertainty on the plane. Discret. Optim.2 (2005) 3–34.  
  15. I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. ORSA J. Comput.12 (2000) 104–110.  
  16. I. Averbakh and O. Berman, Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res.123 (2000) 292–302.  
  17. I. Averbakh and V. Lebedev, Interval data regret network optimization problems. Discr. App. Math.138 (2004) 289–301.  
  18. I. Averbakh and V. Lebedev, On the complexity of minmax regret linear programming. Eur. J. Oper. Res.160 (2005) 227–231.  
  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.  
  21. D. Bertsimas and M. Sim, The price of robustness. Oper. Res.52 (2004) 35–53.  
  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.  
  23. R.E. Burkard and H. Dollani, A note on the robust 1-center problem on trees. Disc. Appl. Math.138 (2004) 289–301.  
  24. A. Candia-Véjar and E. Álvarez-Miranda, On a class of interval data minmax regret CO problems. 2007 (2007) 123–128.  
  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.  
  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.  
  29. X. Chen, J. Hu and X. Hu, A new model for path planning with interval data. Comput. Oper. Res.39 (2009) 1893–1899.  
  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.  
  31. E. Conde, On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett.33 (2005) 481–485.  
  32. E. Conde, Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res.179 (2007) 1025–1039.  
  33. E. Conde, A branch and Bound algorithm for minimum spanning arborescences. J. Glob. Optim.37 (2007) 467–480.  
  34. E. Conde, A note on the minmax regret centdian location on trees. Oper. Res. Lett.36 (2008) 271–275.  
  35. E. Conde, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. Oper. Res. Lett.38 (2010) 326–327.  
  36. E. Conde and A. Candia, Minimax regret spanning arborescences under uncertain costs. Eur. J. Oper. Res.182 (2007) 561–577.  
  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.  
  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).  
  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.  
  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.  
  45. A. Kasperski and P. Zieliński, On combinatorial optimization problems on matroids with uncertain weights. Eur. J. Oper. Res.177 (2007) 851–864.  
  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.  
  47. P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers (1997).  
  48. R. Loulou and A. Kanudia, Minimax regret strategies for greenhouse gas abatement: methodology and application. Oper. Res. Lett.25 (1999) 219–230.  
  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.  
  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.  
  53. R. Montemanni, A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res.174 (2006) 1479–1490.  
  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.  
  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.  
  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.  
  57. R. Montemanni and L.M. Gambardella, The robust shortest path problem with interval data via Benders decomposition, 40R3 (2005) 315–328.  
  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.  
  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 
  64. M. Salazar-Neumann, The robust minimum spanning tree problem: Compact and convex uncertainty. Oper. Res. Lett.35 (2007) 17–22.  
  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.  
  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.  

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.