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

Abstract

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

How to cite

top

Baï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. [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. [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. [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. [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. [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. [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. [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. [8] V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math.4 (1973) 305–337. Zbl0253.05131MR313080
  9. [9] G. Cornuejols and J.-M. Thizy, Some facets of the simple plant location polytope. Math. Progr.23 (1982) 50–74. Zbl0485.90069MR654660
  10. [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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.