Skip to main content
SpringerLink
Log in

Obtaining Sharp Lower and Upper Bounds for Two-Stage Capacitated Facility Location Problems

  • Conference paper
Advances in Distribution Logistics

Part of the book series: Lecture Notes in Economics and Mathematical Systems ((LNE,volume 460))

Abstract

The Two-Stage Capacitated Facility Location Problem (TSCFLP) is to find the optimal locations of depots to serve customers with a given demand, the optimal assignment of customers to depots and the optimal product flow from plants to depots. To compute an optimal solution to the problem, Benders’ decomposition has been the preferred technique. In this paper, a Lagrangean heuristic is proposed to produce good suboptimal solutions together with a lower bound. Lower bounds are computed from the Lagrangean relaxation of the capacity constraints. The Lagrangean subproblem is an Uncapacitated Facility Location Problem (UFLP) with an additional knapsack constraint. From an optimal solution of this subproblem, a heuristic solution to the TSCFLP is computed by reassigning customers until the capacity constraints are met and by solving the transportation problem for the first distribution stage. The Lagrangean dual is solved by a variant of Dantzig-Wolfe decomposition, and elements of cross decomposition are used to get a good initial set of dual cuts.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  • Aardal, K. (1994): Capacitated Facility Location: Separation Algorithm and Computational Experience. CentER Discussion Paper 9480, Tilburg. (available via ftp on ftp://ftp.cs.ruu.nl/pub/ruu/cs/techreps).

    Google Scholar 

  • Aardal, K./Labbé, M./Leung, J./Queyranne, M. (1994): On the Two-Level Uncapacitated Facility Location Problem. CentER Discussion Paper 9486, Tilburg. (available via ftp on ftp://ftp.cs.ruu.nl/pub/ruu/cs/techreps).

    Google Scholar 

  • Aardal, K./Pochet, Y./Wolsey, L. A. (1993): Capacitated Facility Location: Valid Inequalities and Facets. Mathematics of Operations Research, 20:552–582.

    Google Scholar 

  • Balas, E./Martin, R. (1980): Pivot and Complement: A Heuristic for 0–1 Programming. Management Science, 26:86–96.

    Article  Google Scholar 

  • Barcelo, J./Casanovas, J. (1984): A Heuristic Lagrangean Algorithm for the Capacitated Plant Location Problem. European Journal of Operational Research, 15:212–226.

    Article  Google Scholar 

  • Barcelo, J./Fernandez, E./Jörnsten, K. (1991): Computational Results from a New Lagrangean Relaxation Algorithm for the Capacitated Plant Location Problem. European Journal of Operational Research, 52:38–45.

    Article  Google Scholar 

  • Barcelo, J./Hallefjord, Å./Fernandez, E./Jörnsten, K. (1990): Lagrangean Relaxation and Constraint Generation Procedures for Capacitated Plant Location Problems with Single Sourcing. Operations Research-Spektrum, 12:79–88.

    Article  Google Scholar 

  • Benders, J. F. (1962): Partitioning Procedures for Solving Mixed-Variables Programming Problems. Numerische Mathematik, 4:238–252.

    Article  Google Scholar 

  • Cho, D. C./Johnson, E. L./Padberg, M. W./Rao, M. R. (1983a): On the Uncapacitated Plant Location Problem I: Valid Inequalities and Facets. Mathematics of Operations Research, 8:579–589.

    Article  Google Scholar 

  • Cho, D. С./Johnson, E. L./Padberg, M. W./Rao, M. R. (1983b):

    Google Scholar 

  • On the Uncapacitated Plant Location Problem II: Facets and Lifting Theorems. Mathematics of Operations Research, 8:590–612.

    Google Scholar 

  • Cornuejols, G./Fisher, M. L./Nemhauser, G. L. (1977): On the Uncapacitated Location Problem. Annals of Discrete Mathematics, 1:163–177.

    Article  Google Scholar 

  • Cornuejols, G./Thizy, J.-M. (1982): Some Facets of the Simple Plant Location Polytope. Mathematical Programming, 23:50–74.

    Article  Google Scholar 

  • Francis, R. L./McGinnis, L. F./White, J. A. (1992): Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs NJ.

    Google Scholar 

  • Geoffrion, A. M./Graves, G. W. (1974): Multicommodity Distribution System Design by Benders Decomposition. Management Science, 20:822–844.

    Article  Google Scholar 

  • Gu, Z./Nemhauser, G. L./Savelsbergh, M. W. P. (1995): Lifted Cover Inequalities for 0–1 Linear Programs: Computation. Report 94–09, Logistic Optimization Center, Georgia Institute of Technology (available on http://akula.isye.gatech.edu:80/~mwps/).

    Google Scholar 

  • Guignard, M. (1980): Fractional Vertices, Cuts and Facets of the Simple Plant Location Problem. Mathematical Programming Study, 12:150–162.

    Article  Google Scholar 

  • Guignard, M./Opaswongkarn, K. (1990): Lagrangean Dual Ascent Algorithms for Computing Bounds in Capacitated Plant Location Problems. European Journal of Operational Research, 46:73–83.

    Article  Google Scholar 

  • Guignard, M./Rosenwein, M. В. (1989): An Application-Oriented Guide for Designing Lagrangean Dual Ascent Algorithms. European Journal of Operational Research, 43:197–205.

    Article  Google Scholar 

  • Hillier, F. S. (1969): Efficient Heuristic Procedures for Integer Linear Programming. Operations Research, 17:600–637.

    Article  Google Scholar 

  • Hindi, K. S./Basta, T. (1994): Computationally Efficient Solution of a Multiproduct, Two-Stage Distribution-Location Problem. The Journal of the Operational Research Society, 45:1316–1323.

    Google Scholar 

  • Holmberg, K. (1990): On the Convergence of Cross Decomposition. Mathematical Programming, 47:269–296.

    Article  Google Scholar 

  • Holmberg, K. (1992a): Generalized Cross Decomposition Applied to Nonlinear Integer Programming Problems: Duality Gaps and Convexification in Parts. Optimization, 23:341–356.

    Article  Google Scholar 

  • Holmberg, K. (1992b): Linear Mean Value Cross Decomposition: A Generalization of the Kornai-Liptak Method. European Journal of Operational Research, 62:55–73.

    Article  Google Scholar 

  • Holmberg, K. (1994): Cross Decomposition Applied to Integer programming Problems: Duality Gaps and Convexification in Parts. Operations Research, 42:657–668.

    Article  Google Scholar 

  • Kuncewicz, J. G./Luss, H. (1986): A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single Source Constraints. The Journal of the Operational Research Society, 37:495–500.

    Google Scholar 

  • Klose, A. (1994): A Branch and Bound Algorithm for an Uncapacitated Facility Location Problem with a Side Constraint. Working paper, Institut für Unternehmensforschung (Operations Research), Hochschule St. Gallen.

    Google Scholar 

  • Krarup, J./Pruzan, P. M. (1983): The Simple Plant Location Problem: Survey and Synthesis. European Journal of Operational Research, 12:36–81.

    Article  Google Scholar 

  • Leung, J. M. Y./Magnanti, T. L. (1989): Valid Inequalities and Facets of the Capacitated Plant Location Problem. Mathematical Programming, 44:271–291.

    Article  Google Scholar 

  • Magnanti, T. L./Wong, R. T. (1981): Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria. Operations Research, 29:464–484.

    Article  Google Scholar 

  • Magnanti, T. L./Wong, R. T. (1989): Decomposition Methods for Facility Location Problems. In: P. B. Mirchandani and R. L. Francis, editors, Discrete Location Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, pages 209–262. John Wiley & Sons, Chichester New York.

    Google Scholar 

  • Martello, S./Toth, P. (1990): Knapsack Problems — Algorithms and Computer Implementations. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Chichester New York.

    Google Scholar 

  • McDaniel, D./Devine, M. (1977): A Modified Benders’ Partitioning Algorithm for Mixed Integer Programming. Management Science, 24:312–319.

    Article  Google Scholar 

  • Nemhauser, G. L./Wolsey, L. A. (1988): Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Chichester New York.

    Google Scholar 

  • Osman, I. H. (1995): Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches. Operations Research-Spektrum, 17:211–225.

    Article  Google Scholar 

  • Sridharan, R. (1993): A Lagrangian Heuristic for the Capacitated Plant Location Problem with Single Source Constraints. European Journal of Operational Research, 66:305–312.

    Article  Google Scholar 

  • Van Roy, T. J. (1980): Cross Decomposition for Large-Scale, Mixed Integer Linear Programming with Application to Facility Location on Distribution Networks. PhD thesis, Katholieke Universiteit Leuven, Leuven.

    Google Scholar 

  • Van Roy, T. J. (1983): Cross Decomposition for Mixed Integer Programming. Mathematical Programming, 25:46–63.

    Article  Google Scholar 

  • Van Roy, T. J. (1986): A Cross Decomposition Algorithm for Capacitated Facility Location. Operations Research, 34:145–163.

    Article  Google Scholar 

  • Wentges, P. (1994): Standortprobleme mit Berücksichtigung von Kapazitätsrestriktionen: Modellierung und Lösungsverfahren. Dissertation Nr. 1620, Hochschule St. Gallen.

    Google Scholar 

  • Wentges, P. (1996): Accelerating Benders’ Decomposition for the Capacitated Facility Location Problem. Mathematical Methods of Operations Research, 44:267–290.

    Article  Google Scholar 

  • Wentges, P. (1997): Weighted Dantzig-Wolfe Decomposition for Linear Mixed-Integer Programming. International Transactions in Operational Research, 4:151–162.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität St. Gallen, 9000, St. Gallen, Switzerland

    Andreas Klose

Authors
  1. Andreas Klose
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute for Production and Logistics, University of Augsburg, Universitätsstraße 16, D-86135, Augsburg, Germany

    Bernhard Fleischmann

  2. Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, NL-3000 DR, Rotterdam, The Netherlands

    Jo A. E. E. van Nunen

  3. Department of Quantitative Methods, University of Brescia, C. da S. Chiara 48b, I-25122, Brescia, Italy

    M. Grazia Speranza

  4. Institute for Operations Research, University of St. Gallen, Bodanstraße 6, CH-900, St. Gallen, Switzerland

    Paul Stähly

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Klose, A. (1998). Obtaining Sharp Lower and Upper Bounds for Two-Stage Capacitated Facility Location Problems. In: Fleischmann, B., van Nunen, J.A.E.E., Speranza, M.G., Stähly, P. (eds) Advances in Distribution Logistics. Lecture Notes in Economics and Mathematical Systems, vol 460. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-46865-0_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-46865-0_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64288-6

  • Online ISBN: 978-3-642-46865-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation