Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

New facets for the two-stage uncapacitated facility location polytope

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots. In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted fans, is tested with success.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aardal, K., Labbé, M., Leung, J., Queyranne, M.: On the two-level uncapacitated facility location problem. INFORMS J. Comput. 8(3), 289–301 (1996)

    Article  MATH  Google Scholar 

  2. Barahona, F., Mahjoub, A.R.: Compositions of graphs and polyhedra II: Stable sets. SIAM J. Discrete Math. 7, 359–371 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  3. Barros, A.I., Labbé, M.: A general model for the uncapacitated facility and depot location problem. Location Sci. 2, 173–191 (1994)

    MATH  Google Scholar 

  4. Baumol, W.J., Wolfe, P.: A warehouse-location problem. Oper. Res. 6, 252–263 (1958)

    Article  MathSciNet  Google Scholar 

  5. Bloemhof-Ruwaard, J.M., Salomon, M., Van Wassenhove, L.N.: On the coordination of product and by-product flows in two level distribution networks: model formulation and solution procedures. Eur. J. Oper. Res. 79, 325–339 (1994)

    Article  MATH  Google Scholar 

  6. Bloemhof-Ruwaard, J.M., Salomon, M., Van Wassenhove, L.N.: The capacitated distribution and waste disposal problem. Eur. J. Oper. Res. 88, 490–503 (1996)

    Article  MATH  Google Scholar 

  7. Bumb, A.: An approximation algorithm for the maximization version of the two level uncapacitated facility location problem. Oper. Res. Lett. 29, 155–161 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cánovas, L., Landete, M., Marín, A.: New facets for the set packing polytope. Oper. Res. Lett. 27(4), 153–161 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  9. Cánovas, L., Landete, M., Marín, A.: Facet obtaining procedures for set packing problems. SIAM J. Discrete Math. 16(1), 127–155 (2003)

    Article  MATH  Google Scholar 

  10. Chardaire, P., Lutton, J.-L., Sutter, A.: Upper and lower bounds for the two-level simple plant location problem. Ann. Oper. Res. 86, 117–140 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  11. Cheng, E., Cunningham, W.H.: Wheel inequalities for stable set polytopes. Math. Program. 77, 389–421 (1997)

    MathSciNet  Google Scholar 

  12. Cho, D.C., Johnson, E.L., Padberg, M.W., Rao, M.R.: On the uncapacitated plant location problem I: Valid inequalities and facets. Math. Oper. Res. 8(4), 579–589 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  13. Crainic, T.G., Delorme, L.: Dual-ascent procedures for multicommodity location–allocation problems with balancing requirements. Transp. Sci. 27, 90–101 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  14. Elson, D.G.: Site location via mixed-integer programming. Oper. Res. Q. 23(1), 31–43 (1972)

    Article  MATH  Google Scholar 

  15. Gao, L.-L., Robinson, E.P. Jr.: A dual-based optimization procedure for the two-echelon uncapacitated facility location problem. Nav. Res. Logist. 39, 191–212 (1992)

    Article  MATH  Google Scholar 

  16. Gao, L.-L., Robinson, E.P. Jr.: Uncapacitated facility location: General solution procedure and computational experience. Eur. J. Oper. Res. 76, 410–427 (1994)

    Article  MATH  Google Scholar 

  17. Gendron, B., Crainic, T.G.: A branch-and-bound algorithm for depot location and container fleet management. Location Sci. 3, 39–53 (1995)

    Article  MATH  Google Scholar 

  18. Gendron, B., Crainic, T.G.: A parallel branch-and-bound algorithm for multicommodity location with balancing requirements. Comput. Oper. Res. 24, 829–847 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  19. Geoffrion, A.M., Graves, G.W.: Multicommodity distribution system design by Benders decomposition. Manag. Sci. 20, 822–844 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  20. Guignard, M.: Fractional vertices, cuts and facets of the simple plant location problem. Math. Progam. Study 12, 150–162 (1980)

    MATH  MathSciNet  Google Scholar 

  21. Hinojosa, Y., Puerto, J., Fernández, F.R.: A multiperiod two-echelon multicommodity capacitated plant location problem. Eur. J. Oper. Res. 123, 271–291 (2000)

    Article  MATH  Google Scholar 

  22. Kaufman, L., Eede, M.V., Hansen, P.: A plant and warehouse location problem. Oper. Res. Q. 28, 547–554 (1977)

    Article  MATH  Google Scholar 

  23. Klincewicz, J.G.: A large-scale distribution and location model. ATT Techn. J. 64(7), 1705–1730 (1985)

    Google Scholar 

  24. Klose, A.: An LP-based heuristic for two-stage capacitated facility location problems. J. Oper. Res. Soc. 50, 157–166 (1999)

    Article  MATH  Google Scholar 

  25. Klose, A.: A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem. Eur. J. Oper. Res. 126, 408–421 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  26. Marín, A.: Lower bounds for the two-stage uncapacitated facility location problem. Eur. J. Oper. Res. 179, 1126–1142 (2007)

    Article  MATH  Google Scholar 

  27. Marín, A., Pelegrín, B.: A branch-and-bound algorithm for the transportation problem with location of p transshipment points. Comput. Oper. Res. 7, 659–678 (1997)

    Article  Google Scholar 

  28. Marín, A., Pelegrín, B.: The return plant location problem: Modelling and resolution. Eur. J. Oper. Res. 104(2), 375–392 (1998)

    Article  MATH  Google Scholar 

  29. Marín, A., Pelegrín, B.: Applying Lagrangean relaxation to the resolution of two-stage location problems. Ann. Oper. Res. 86, 179–198 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  30. Moon, S.: A profit-maximizing plant-loading model with demand fill-rate constraints. J. Oper. Res. Soc. 40(11), 1019–1027 (1989)

    Article  MATH  Google Scholar 

  31. Nemhauser, G.L., Trotter, L.E. Jr.: Properties of vertex packing and independence system polyhedra. Math. Program. 6, 48–61 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  32. Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5, 199–215 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  33. Padberg, M.W.: A note on zero-one programming. Oper. Res. 23, 833–837 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  34. Padberg, M.W.: On the complexity of set packing polyhedra. Ann. Discrete Math. 1, 421–434 (1977)

    Article  MathSciNet  Google Scholar 

  35. Pirkul, H., Jayaraman, V.: Production, transportation, and distribution planning in a multi-commodity tri-echelon system. Transp. Sci. 30(4), 291–302 (1996)

    Article  MATH  Google Scholar 

  36. Pirkul, H., Jayaraman, V.: A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Comput. Oper. Res. 25(10), 869–878 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  37. Ro, H., Tcha, D.: A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints. Eur. J. Oper. Res. 18, 349–358 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  38. Tragantalerngsak, S., Holt, J., Ronnqvist, M.: Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem. Eur. J. Oper. Res. 102, 611–625 (1997)

    Article  MATH  Google Scholar 

  39. Trotter, L.E.: A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12, 373–388 (1975)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Estadística y Matemática Aplicada, Centro de Investigación Operativa, Universidad Miguel Hernández, Elche, Spain

    Mercedes Landete

  2. Departamento de Estadística e Investigación Operativa, Facultad de Matemáticas, Campus de Espinardo, Universidad de Murcia, Murcia, Spain

    Alfredo Marín

Authors
  1. Mercedes Landete
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alfredo Marín
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alfredo Marín.

Additional information

The authors would like to acknowledge that research reported here was supported by Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+D+I), project MTM2006-14961-C05-04 and RDEF funds, and Fundación Séneca project 02911/PI/05. The authors are grateful to two referees and an associated editor for having generously given their time in evaluating the manuscript and doing insightful suggestions which helped us to improve it.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Landete, M., Marín, A. New facets for the two-stage uncapacitated facility location polytope. Comput Optim Appl 44, 487–519 (2009). https://doi.org/10.1007/s10589-008-9165-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9165-x

Keywords

Search

Navigation