Lexicographic α-robustness: an application to the 1-median problem

R. Kalaï; M. A. Aloulou; Ph. Vallin; D. Vanderpooten

RAIRO - Operations Research (2010)

  • Volume: 44, Issue: 2, page 119-138
  • ISSN: 0399-0559

Abstract

top
In the last decade, several robustness approaches have been developed to deal with uncertainty. In decision problems, and particularly in location problems, the most used robustness approach rely either on maximal cost or on maximal regret criteria. However, it is well known that these criteria are too conservative. In this paper, we present a new robustness approach, called lexicographic α-robustness, which compensates for the drawbacks of criteria based on the worst case. We apply this approach to the 1-median location problem under uncertainty on node weights and we give a specific algorithm to determine robust solutions in the case of a tree. We also show that this algorithm can be extended to the case of a general network.

How to cite

top

Kalaï, R., et al. "Lexicographic α-robustness: an application to the 1-median problem." RAIRO - Operations Research 44.2 (2010): 119-138. <http://eudml.org/doc/250861>.

@article{Kalaï2010,
abstract = { In the last decade, several robustness approaches have been developed to deal with uncertainty. In decision problems, and particularly in location problems, the most used robustness approach rely either on maximal cost or on maximal regret criteria. However, it is well known that these criteria are too conservative. In this paper, we present a new robustness approach, called lexicographic α-robustness, which compensates for the drawbacks of criteria based on the worst case. We apply this approach to the 1-median location problem under uncertainty on node weights and we give a specific algorithm to determine robust solutions in the case of a tree. We also show that this algorithm can be extended to the case of a general network. },
author = {Kalaï, R., Aloulou, M. A., Vallin, Ph., Vanderpooten, D.},
journal = {RAIRO - Operations Research},
keywords = {Robustness; 1-median location problem; minmax cost/regret; robustness},
language = {eng},
month = {4},
number = {2},
pages = {119-138},
publisher = {EDP Sciences},
title = {Lexicographic α-robustness: an application to the 1-median problem},
url = {http://eudml.org/doc/250861},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Kalaï, R.
AU - Aloulou, M. A.
AU - Vallin, Ph.
AU - Vanderpooten, D.
TI - Lexicographic α-robustness: an application to the 1-median problem
JO - RAIRO - Operations Research
DA - 2010/4//
PB - EDP Sciences
VL - 44
IS - 2
SP - 119
EP - 138
AB - In the last decade, several robustness approaches have been developed to deal with uncertainty. In decision problems, and particularly in location problems, the most used robustness approach rely either on maximal cost or on maximal regret criteria. However, it is well known that these criteria are too conservative. In this paper, we present a new robustness approach, called lexicographic α-robustness, which compensates for the drawbacks of criteria based on the worst case. We apply this approach to the 1-median location problem under uncertainty on node weights and we give a specific algorithm to determine robust solutions in the case of a tree. We also show that this algorithm can be extended to the case of a general network.
LA - eng
KW - Robustness; 1-median location problem; minmax cost/regret; robustness
UR - http://eudml.org/doc/250861
ER -

References

top
  1. I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge length. Discrete Appl. Math.127 (2003) 505–522.  
  2. I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. Informs J. Comput.12 (2000) 104–110.  
  3. I. Averbakh and O. Berman, An improved algorithm for the minmax regret median problem on a tree. Networks41 (2003) 97–103.  
  4. D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program., Ser. B 98 (2003) 49–71.  
  5. G.S. Brodal, L. Georgiadis and I. Katriel, An O(n log n) version of the Averbakh-Berman algorithm for the robust median on a tree. Oper. Res. Lett.36 (2008) 14–18.  
  6. R.E. Burkard and H. Dollani, Robust location problems with pos/neg weights on a tree. Networks38 (2001) 102–113.  
  7. B. Chen and C.S. Lin, Min-max regret robust 1-median location on a tree. Networks31 (1998) 93–103.  
  8. M.S. Daskin, Network and Discrete Location: Models, Algorithms and Applications. Wiley (1995).  
  9. M.S. Daskin, S.M. Hesse and C.S. Revelle, α-reliable p-minimax regret: a new model for strategic facility location modeling. Location Science5 (1997) 227–246.  
  10. H. Edelsbrunner and L.J. Guibas, Topologically sweeping an arrangement. J. Comput. Syst. Sci.38 (1989) 165–194. Corrigendum in 42 (1991) 249–251.  
  11. P.C. Fishburn Lexicographic orders, utilities and decision rules: a survey. Manage. Sci.20 (1974) 1442–1471.  
  12. M. Grabisch and P. Perny Agrégation multicritère, in Logique Floue, principes, aide à la décision, edited by B. Bouchon-Meunier and C. Marsala. Hermès-Lavoisier (2003) 81–120.  
  13. S.L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res.12 (1964) 450–459.  
  14. C. Harries, Correspondence to what? coherence to what? what is good scenario-based decision making? Technol. Forecast. Soc. Change70 (2003) 797–817.  
  15. R. Kalaï, Une nouvelle approche de robustesse: application à quelques problèmes d'optimisation. Ph.D. thesis, Université Paris-Dauphine, France (2006).  
  16. R. Kalaï and D. Vanderpooten Lexicographic α-robust knapsack problem: Complexity results, in International Conference on Service Systems & Service Management (IEEE SSSM'06), Troyes, France, October (2006).  
  17. P. Kouvelis, A.A. Kurawarwala and G.J. Gutiérrez Algorithms for robust single and multiple period layout planning for manufacturing systems. Eur. J. Oper. Res.63 (1992) 287–303.  
  18. P. Kouvelis, G. Vairaktarakis and G. Yu, Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty. Working paper 93/94-3-4, Department of Management Science and Information Systems, University of Texas at Austin (1994).  
  19. P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publishers (1997).  
  20. H. Moulin, Social welfare orderings, in Axioms of cooperative decision making, Cambridge University Press (1988) pp. 30–60.  
  21. J.M. Mulvey, R.J. Vanderbei and S.A. Zenios Robust optimization of large-scale systems. Oper. Res.43 (1995) 264–281.  
  22. W. Ogryczak, On the lexicographic minimax approach to location problems. Eur. J. Oper. Res.100 (1997) 566–585.  
  23. W. Ogryczak, Multiple criteria optimization and decisions under risk. Control and Cybernetics31 (2002) 975–1003.  
  24. P. Perny, O. Spanjaard and L.X. Storme, A decision-theoretic approach to robust optimization in multivalued graphs. Ann. Oper. Res.147 (2006) 317–341.  
  25. J.-C. Pomerol, Scenario development and practical decision making under uncertainty. Decis. Support Syst.31 (2001) 197–204.  
  26. J. Puerto, A.M. Rodriguez-Chia and A. Tamir, Minimax regret single-facility ordered median location problems on networks. Informs J. Comput.21 (2009) 77–87.  
  27. E. Rafalin, D. Souvaine and I. Streinu Topological sweep in degenerate cases, in Proc. of the 4th international workshop on Algorithm Engineering and Experiments, ALENEX02, in Lect. Notes Comput. Sci. 2409, Springer-Verlag (2002) 155–156.  
  28. B. Roy, A missing link in OR-DA: robustness analysis. Found. Comput. Decis. Sci.23 (1998) 141–160.  
  29. B. Roy and Ph. Vincke, Relational systems of preference with one or more pseudo-criteria: some new concepts and results. Manage. Sci.30 (1984) 1323–1335.  
  30. J.-R. Sack and J. Urrutia (Eds.), Handbook of Computational Geometry. Elsevier Sciences (2000).  
  31. P.J.H. Schoemaker, Multiple scenario development: Its conceptual and behavioral foundation. Strateg. Manage. J.14 (1993) 193–213.  
  32. L.V. Snyder and M.S. Daskin, Stochastic p-robust location problems. IIE Trans.38 (2006) 971–985.  
  33. G.L. Vairaktarakis and P. Kouvelis, Incorporating dynamic aspects and uncertainty in 1-median location problems. Nav. Res. Logist.46 (1999) 147–168.  
  34. P. Vincke, Robust solutions and methods in decision-aid. J. Multi-Crit. Decis. Anal.8 (1999) 181–187.  
  35. H. Yaman, O.E. Karasan and M.C. Pinar, Restricted robust optimization for maximization over uniform matroid with interval data uncertainty. Technical report, Bilkent University, Department of Industrial Engineering, Bilkent, Turkey (2005).  

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.