# 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

## Access Full Article

top## Abstract

top## How to cite

topKalaï, 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- I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge length. Discrete Appl. Math.127 (2003) 505–522. Zbl1038.90041
- I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. Informs J. Comput.12 (2000) 104–110. Zbl1034.90007
- I. Averbakh and O. Berman, An improved algorithm for the minmax regret median problem on a tree. Networks41 (2003) 97–103. Zbl1028.90081
- D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program., Ser. B 98 (2003) 49–71. Zbl1082.90067
- 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.
- R.E. Burkard and H. Dollani, Robust location problems with pos/neg weights on a tree. Networks38 (2001) 102–113. Zbl0990.90060
- B. Chen and C.S. Lin, Min-max regret robust 1-median location on a tree. Networks31 (1998) 93–103. Zbl0930.90050
- M.S. Daskin, Network and Discrete Location: Models, Algorithms and Applications. Wiley (1995). Zbl0870.90076
- 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. Zbl0917.90231
- H. Edelsbrunner and L.J. Guibas, Topologically sweeping an arrangement. J. Comput. Syst. Sci.38 (1989) 165–194. Corrigendum in 42 (1991) 249–251. Zbl0676.68013
- P.C. Fishburn Lexicographic orders, utilities and decision rules: a survey. Manage. Sci.20 (1974) 1442–1471.
- 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.
- S.L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res.12 (1964) 450–459. Zbl0123.00305
- C. Harries, Correspondence to what? coherence to what? what is good scenario-based decision making? Technol. Forecast. Soc. Change70 (2003) 797–817.
- R. Kalaï, Une nouvelle approche de robustesse: application à quelques problèmes d'optimisation. Ph.D. thesis, Université Paris-Dauphine, France (2006).
- 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).
- 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. Zbl0825.90472
- 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).
- P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publishers (1997). Zbl0873.90071
- H. Moulin, Social welfare orderings, in Axioms of cooperative decision making, Cambridge University Press (1988) pp. 30–60.
- J.M. Mulvey, R.J. Vanderbei and S.A. Zenios Robust optimization of large-scale systems. Oper. Res.43 (1995) 264–281. Zbl0832.90084
- W. Ogryczak, On the lexicographic minimax approach to location problems. Eur. J. Oper. Res.100 (1997) 566–585. Zbl0921.90106
- W. Ogryczak, Multiple criteria optimization and decisions under risk. Control and Cybernetics31 (2002) 975–1003. Zbl1180.90157
- 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. Zbl1189.90020
- J.-C. Pomerol, Scenario development and practical decision making under uncertainty. Decis. Support Syst.31 (2001) 197–204.
- 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. Zbl1243.90032
- 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.
- B. Roy, A missing link in OR-DA: robustness analysis. Found. Comput. Decis. Sci.23 (1998) 141–160. Zbl0967.90077
- 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. Zbl0555.90002
- J.-R. Sack and J. Urrutia (Eds.), Handbook of Computational Geometry. Elsevier Sciences (2000). Zbl0930.65001
- P.J.H. Schoemaker, Multiple scenario development: Its conceptual and behavioral foundation. Strateg. Manage. J.14 (1993) 193–213.
- L.V. Snyder and M.S. Daskin, Stochastic p-robust location problems. IIE Trans.38 (2006) 971–985.
- G.L. Vairaktarakis and P. Kouvelis, Incorporating dynamic aspects and uncertainty in 1-median location problems. Nav. Res. Logist.46 (1999) 147–168. Zbl0918.90101
- P. Vincke, Robust solutions and methods in decision-aid. J. Multi-Crit. Decis. Anal.8 (1999) 181–187. Zbl0946.90042
- 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). Zbl1116.90080

## NotesEmbed ?

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