Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation

Andreas Klose () and Andreas Drexl ()
Additional contact information
Andreas Klose: Institute for Operations Research, University of Zurich, 8044 Zurich, Switzerland
Andreas Drexl: Institute of Business Administration, University of Kiel, 24098 Kiel, Germany

Management Science, 2005, vol. 51, issue 11, 1689-1705

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, information about a primal (fractional) solution can be important to solve large or difficult problem instances. Therefore, we study various 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.

Keywords: capacitated facility location problem; integer programming; Lagrangean relaxation; column generation (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1050.0410 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:51:y:2005:i:11:p:1689-1705

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().