A polyhedral study of a two level facility location model
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 153-165.

We study an uncapacitated facility location model where customers are served by facilities of level one, then each level one facility that is opened must be assigned to an opened facility of level two. We identify a polynomially solvable case, and study some valid inequalities and facets of the associated polytope.

DOI : 10.1051/ro/2014003
Classification : 05C85, 90C27
Mots-clés : uncapacitated facility location problem, two level facility location 
@article{RO_2014__48_2_153_0,
     author = {Ba{\"\i}ou, Mourad and Barahona, Francisco},
     title = {A polyhedral study of a two level facility location model},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {153--165},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {2},
     year = {2014},
     doi = {10.1051/ro/2014003},
     mrnumber = {3264373},
     zbl = {1294.05145},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014003/}
}
TY  - JOUR
AU  - Baïou, Mourad
AU  - Barahona, Francisco
TI  - A polyhedral study of a two level facility location model
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2014
SP  - 153
EP  - 165
VL  - 48
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014003/
DO  - 10.1051/ro/2014003
LA  - en
ID  - RO_2014__48_2_153_0
ER  - 
%0 Journal Article
%A Baïou, Mourad
%A Barahona, Francisco
%T A polyhedral study of a two level facility location model
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 153-165
%V 48
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014003/
%R 10.1051/ro/2014003
%G en
%F RO_2014__48_2_153_0
Baïou, Mourad; Barahona, Francisco. A polyhedral study of a two level facility location model. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 153-165. doi : 10.1051/ro/2014003. http://www.numdam.org/articles/10.1051/ro/2014003/

[1] K. Aardal, F.A. Chudak and D.B. Shmoys, A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform. Process. Lett. 72 (1999) 161-167. | MR | Zbl

[2] K. Aardal, M. Labbé, J. Leung and M. Queyranne, On the two-level uncapacitated facility location problem. INFORMS J. Comput. 8 (1996) 289-301. | Zbl

[3] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows, Theory, algorithms, and applications, Prentice Hall Inc., Englewood Cliffs, NJ (1993). | MR | Zbl

[4] M. Baïou and F. Barahona, On the integrality of some facility location polytopes. SIAM J. Discrete Math. 23 (2009) 665-679. | MR | Zbl

[5] L. Cánovas, M. Landete and A. Marín, On the facets of the simple plant location packing polytope. Discrete Appl. Math. 124 (2002) 27-53. | MR | Zbl

[6] D.C. Cho, E.L. Johnson, M. Padberg and M.R. Rao, On the uncapacitated plant location problem. I. Valid inequalities and facets. Math. Oper. Res. 8 (1983) 579-589. | MR | Zbl

[7] D.C. Cho, M.W. Padberg and M.R. Rao, On the uncapacitated plant location problem II. Facets and lifting theorems. Math. Oper. Res. 8 (1983) 590-612. | MR | Zbl

[8] V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4 (1973) 305-337. | MR | Zbl

[9] G. Cornuejols and J.-M. Thizy, Some facets of the simple plant location polytope. Math. Progr. 23 (1982) 50-74. | MR | Zbl

[10] E. Kantor and D. Peleg, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems. J. Discrete Algorithms 7 (2009) 341-362. | MR | Zbl

Cité par Sources :