# A polyhedral study of a two level facility location model

Mourad Baïou; Francisco Barahona

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 2, page 153-165
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBaïou, Mourad, and Barahona, Francisco. "A polyhedral study of a two level facility location model." RAIRO - Operations Research - Recherche Opérationnelle 48.2 (2014): 153-165. <http://eudml.org/doc/275075>.

@article{Baïou2014,

abstract = {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.},

author = {Baïou, Mourad, Barahona, Francisco},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {uncapacitated facility location problem; two level facility location},

language = {eng},

number = {2},

pages = {153-165},

publisher = {EDP-Sciences},

title = {A polyhedral study of a two level facility location model},

url = {http://eudml.org/doc/275075},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 2

SP - 153

EP - 165

AB - 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.

LA - eng

KW - uncapacitated facility location problem; two level facility location

UR - http://eudml.org/doc/275075

ER -

## References

top- [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. Zbl0994.90090MR1737753
- [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. Zbl0863.90102
- [3] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows, Theory, algorithms, and applications, Prentice Hall Inc., Englewood Cliffs, NJ (1993). Zbl1201.90001MR1205775
- [4] M. Baïou and F. Barahona, On the integrality of some facility location polytopes. SIAM J. Discrete Math.23 (2009) 665–679. Zbl1198.90332MR2496910
- [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. Zbl1175.90326MR1924950
- [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. Zbl0536.90029MR727413
- [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. Zbl0536.90030MR727414
- [8] V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math.4 (1973) 305–337. Zbl0253.05131MR313080
- [9] G. Cornuejols and J.-M. Thizy, Some facets of the simple plant location polytope. Math. Progr.23 (1982) 50–74. Zbl0485.90069MR654660
- [10] E. Kantor and D. Peleg, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems. J. Discrete Algorithms7 (2009) 341–362. Zbl1187.68348MR2529141