Lexicographic α-robustness : an application to the 1-median problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 2, pp. 119-138.

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.

DOI : 10.1051/ro/2010010
Classification : 90B50
Mots-clés : robustness, 1-median location problem, minmax cost/regret 
@article{RO_2010__44_2_119_0,
     author = {Kala{\"\i}, R. and Aloulou, M. A. and Vallin, Ph. and Vanderpooten, D.},
     title = {Lexicographic $\alpha $-robustness : an application to the 1-median problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {119--138},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {2},
     year = {2010},
     doi = {10.1051/ro/2010010},
     mrnumber = {2666485},
     zbl = {1189.90078},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2010010/}
}
TY  - JOUR
AU  - Kalaï, R.
AU  - Aloulou, M. A.
AU  - Vallin, Ph.
AU  - Vanderpooten, D.
TI  - Lexicographic $\alpha $-robustness : an application to the 1-median problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2010
SP  - 119
EP  - 138
VL  - 44
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2010010/
DO  - 10.1051/ro/2010010
LA  - en
ID  - RO_2010__44_2_119_0
ER  - 
%0 Journal Article
%A Kalaï, R.
%A Aloulou, M. A.
%A Vallin, Ph.
%A Vanderpooten, D.
%T Lexicographic $\alpha $-robustness : an application to the 1-median problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2010
%P 119-138
%V 44
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2010010/
%R 10.1051/ro/2010010
%G en
%F RO_2010__44_2_119_0
Kalaï, R.; Aloulou, M. A.; Vallin, Ph.; Vanderpooten, D. Lexicographic $\alpha $-robustness : an application to the 1-median problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 2, pp. 119-138. doi : 10.1051/ro/2010010. http://www.numdam.org/articles/10.1051/ro/2010010/

[1] I. Averbakh, Complexity of robust single facility location problems on networks with uncertain edge length. Discrete Appl. Math. 127 (2003) 505-522. | Zbl

[2] I. Averbakh and O. Berman, Minmax regret median location on a network under uncertainty. Informs J. Comput. 12 (2000) 104-110. | Zbl

[3] I. Averbakh and O. Berman, An improved algorithm for the minmax regret median problem on a tree. Networks 41 (2003) 97-103. | Zbl

[4] D. Bertsimas and M. Sim, Robust discrete optimization and network flows. Math. Program., Ser. B 98 (2003) 49-71. | Zbl

[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. | Zbl

[6] R.E. Burkard and H. Dollani, Robust location problems with pos/neg weights on a tree. Networks 38 (2001) 102-113. | Zbl

[7] B. Chen and C.S. Lin, Min-max regret robust 1-median location on a tree. Networks 31 (1998) 93-103. | Zbl

[8] M.S. Daskin, Network and Discrete Location: Models, Algorithms and Applications. Wiley (1995). | Zbl

[9] M.S. Daskin, S.M. Hesse and C.S. Revelle, α-reliable p-minimax regret: a new model for strategic facility location modeling. Location Science 5 (1997) 227-246. | Zbl

[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. | MR | Zbl

[11] P.C. Fishburn Lexicographic orders, utilities and decision rules: a survey. Manage. Sci. 20 (1974) 1442-1471. | MR | Zbl

[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. | Zbl

[14] C. Harries, Correspondence to what? coherence to what? what is good scenario-based decision making? Technol. Forecast. Soc. Change 70 (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. | Zbl

[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). | MR | Zbl

[20] H. Moulin, Social welfare orderings, in Axioms of cooperative decision making, Cambridge University Press (1988) pp. 30-60. | MR

[21] J.M. Mulvey, R.J. Vanderbei and S.A. Zenios Robust optimization of large-scale systems. Oper. Res. 43 (1995) 264-281. | MR | Zbl

[22] W. Ogryczak, On the lexicographic minimax approach to location problems. Eur. J. Oper. Res. 100 (1997) 566-585. | Zbl

[23] W. Ogryczak, Multiple criteria optimization and decisions under risk. Control and Cybernetics 31 (2002) 975-1003. | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | Zbl

[28] B. Roy, A missing link in OR-DA: robustness analysis. Found. Comput. Decis. Sci. 23 (1998) 141-160. | Zbl

[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. | MR | Zbl

[30] J.-R. Sack and J. Urrutia (Eds.), Handbook of Computational Geometry. Elsevier Sciences (2000). | MR | Zbl

[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. | MR | Zbl

[34] P. Vincke, Robust solutions and methods in decision-aid. J. Multi-Crit. Decis. Anal. 8 (1999) 181-187. | Zbl

[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).

Cité par Sources :