Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-15T10:26:15.816Z Has data issue: false hasContentIssue false
  • English
  • Français

A polyhedral study of a two level facility location model∗

Published online by Cambridge University Press:  07 March 2014

Mourad Baïou and
Francisco Barahona
Mourad Baïou
Affiliation:
CNRS, LIMOS, and Université Blaise Pascal, Complexe scientifique des Cézeaux, 63173 Aubiere Cedex, France.. mourad.baiou@isima.fr
Francisco Barahona
Affiliation:
IBM T. J. Watson research Center, Yorktown Heights, NY 10589, USA.; barahon@us.ibm.com

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Keywords

Uncapacitated facility location problemtwo level facility location

Information

Type
Research Article
Information
RAIRO - Operations Research , Volume 48 , Issue 2: Isco 2012, guest editors Nelson Maculan, A. Ridha Mahjoub, Eduardo Uchoa , April 2014, pp. 153 - 165
Copyright
© EDP Sciences, ROADEF, SMAI, 2014

References

Aardal, K., Chudak, F.A. and Shmoys, D.B., A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform. Process. Lett. 72 (1999) 161–167. Google Scholar
Aardal, K., Labbé, M., Leung, J. and Queyranne, M., On the two-level uncapacitated facility location problem. INFORMS J. Comput. 8 (1996) 289–301. Google Scholar
R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows, Theory, algorithms, and applications, Prentice Hall Inc., Englewood Cliffs, NJ (1993).
Baïou, M. and Barahona, F., On the integrality of some facility location polytopes. SIAM J. Discrete Math. 23 (2009) 665–679. Google Scholar
Cánovas, L., Landete, M. and Marín, A., On the facets of the simple plant location packing polytope. Discrete Appl. Math. 124 (2002) 27–53. Google Scholar
Cho, D.C., Johnson, E.L., Padberg, M. and Rao, M.R., On the uncapacitated plant location problem. I. Valid inequalities and facets. Math. Oper. Res. 8 (1983) 579–589. Google Scholar
Cho, D.C., Padberg, M.W. and Rao, M.R., On the uncapacitated plant location problem II. Facets and lifting theorems. Math. Oper. Res. 8 (1983) 590–612. Google Scholar
Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4 (1973) 305–337. Google Scholar
Cornuejols, G. and Thizy, J.-M., Some facets of the simple plant location polytope. Math. Progr. 23 (1982) 50–74. Google Scholar
Kantor, E. and Peleg, D., Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems. J. Discrete Algorithms 7 (2009) 341–362. Google Scholar