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.

Keywords: 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://archive.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://archive.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://archive.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, Volume 48 (2014) no. 2, pp. 153-165. doi : 10.1051/ro/2014003. http://archive.numdam.org/articles/10.1051/ro/2014003/

[1] A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform. Process. Lett. 72 (1999) 161-167. | MR | Zbl

, and ,[2] On the two-level uncapacitated facility location problem. INFORMS J. Comput. 8 (1996) 289-301. | Zbl

, , and ,[3] Network flows, Theory, algorithms, and applications, Prentice Hall Inc., Englewood Cliffs, NJ (1993). | MR | Zbl

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

and ,[5] On the facets of the simple plant location packing polytope. Discrete Appl. Math. 124 (2002) 27-53. | MR | Zbl

, and ,[6] On the uncapacitated plant location problem. I. Valid inequalities and facets. Math. Oper. Res. 8 (1983) 579-589. | MR | Zbl

, , and ,[7] On the uncapacitated plant location problem II. Facets and lifting theorems. Math. Oper. Res. 8 (1983) 590-612. | MR | Zbl

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

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

and ,[10] 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

and ,*Cited by Sources: *