IDEAS home Printed from https://ideas.repec.org/p/zbw/cauman/544.html
   My bibliography  Save this paper

Lower bounds for the capacitated facility location problem based on column generation

Author

Listed:
  • Klose, Andreas
  • Drexl, Andreas

Abstract

The Capacitated Facility Location Problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. A variety of lower bounds based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. However, in order to solve large or difficult problem instances information about a primal (fractional) solution can be important. Therefore, we study var-ious approaches for solving the master problems exactly. The algorithms employ different strategies for stabilizing the column generation process. Furthermore, a new lower bound for the CFLP based on partitioning the plant set and employing column generation is proposed. Computational results are reported for a set of large problem instances.

Suggested Citation

  • Klose, Andreas & Drexl, Andreas, 2001. "Lower bounds for the capacitated facility location problem based on column generation," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 544, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    • Handle: RePEc:zbw:cauman:544
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/147622/1/manuskript_544.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    3. Cornuejols, G. & Sridharan, R. & Thizy, J. M., 1991. "A comparison of heuristics and relaxations for the capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 50(3), pages 280-297, February.
    4. Tony J. Van Roy, 1986. "A Cross Decomposition Algorithm for Capacitated Facility Location," Operations Research, INFORMS, vol. 34(1), pages 145-163, February.
    5. Sridharan, R., 1995. "The capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 87(2), pages 203-213, December.
    6. Gondzio, J. & du Merle, O. & Sarkissian, R. & Vial, J. -P., 1996. "ACCPM -- A library for convex optimization based on an analytic center cutting plane method," European Journal of Operational Research, Elsevier, vol. 94(1), pages 206-211, October.
    7. Goffin, J. -L. & Haurie, A. & Vial, J. -Ph. & Zhu, D. L., 1993. "Using central prices in the decomposition of linear programs," European Journal of Operational Research, Elsevier, vol. 64(3), pages 393-409, February.
    8. J. L. Goffin & A. Haurie & J. P. Vial, 1992. "Decomposition and Nondifferentiable Optimization with the Projective Algorithm," Management Science, INFORMS, vol. 38(2), pages 284-302, February.
    9. Kochman, G. A. & McCallum, C. J., 1981. "Facility location models for planning a transatlantic communications network," European Journal of Operational Research, Elsevier, vol. 6(2), pages 205-211, February.
    10. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    2. Klose, Andreas & Drexl, Andreas, 2001. "Combinatorial optimisation problems of the assignment type and a partitioning approach," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 545, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andreas Klose & Andreas Drexl, 2005. "Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation," Management Science, INFORMS, vol. 51(11), pages 1689-1705, November.
    2. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    3. Klose, Andreas, 2000. "A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 126(2), pages 408-421, October.
    4. Klose, Andreas & Drexl, Andreas, 2001. "Combinatorial optimisation problems of the assignment type and a partitioning approach," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 545, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    5. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    6. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Sourirajan, Karthik & Ozsen, Leyla & Uzsoy, Reha, 2009. "A genetic algorithm for a single product network design model with lead time and safety stock considerations," European Journal of Operational Research, Elsevier, vol. 197(2), pages 599-608, September.
    8. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    9. Eskigun, Erdem & Uzsoy, Reha & Preckel, Paul V. & Beaujon, George & Krishnan, Subramanian & Tew, Jeffrey D., 2005. "Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers," European Journal of Operational Research, Elsevier, vol. 165(1), pages 182-206, August.
    10. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    11. Madadi, AliReza & Kurz, Mary E. & Mason, Scott J. & Taaffe, Kevin M., 2014. "Supply chain design under quality disruptions and tainted materials delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 67(C), pages 105-123.
    12. Sune Lauth Gadegaard & Andreas Klose & Lars Relund Nielsen, 2018. "An improved cut-and-solve algorithm for the single-source capacitated facility location problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 1-27, March.
    13. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    14. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    15. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    16. Samir Elhedhli & Jean-Louis Goffin, 2005. "Efficient Production-Distribution System Design," Management Science, INFORMS, vol. 51(7), pages 1151-1164, July.
    17. Gondzio, J. & du Merle, O. & Sarkissian, R. & Vial, J. -P., 1996. "ACCPM -- A library for convex optimization based on an analytic center cutting plane method," European Journal of Operational Research, Elsevier, vol. 94(1), pages 206-211, October.
    18. Sharma, R.R.K. & Berry, V., 2007. "Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort," European Journal of Operational Research, Elsevier, vol. 177(2), pages 803-812, March.
    19. Yong Liang & Mengshi Lu & Zuo‐Jun Max Shen & Runyu Tang, 2021. "Data Center Network Design for Internet‐Related Services and Cloud Computing," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2077-2101, July.
    20. Fathali Firoozi, 2008. "Boundary Distributions in Testing Inequality Hypotheses," Working Papers 0046, College of Business, University of Texas at San Antonio.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:zbw:cauman:544. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/ibkiede.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.