An Exact Column Generation Approach to the Capacitated Facility Location Problem

Andreas Klose and Simon Görtz
Additional contact information
Andreas Klose: University of Zurich
Simon Görtz: University of Wuppertal

A chapter in Distribution Logistics, 2005, pp 3-26 from Springer

Abstract: Abstract The Capacitated Facility Location Problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. 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 is important. Therefore, we employ column generation in order to solve a corresponding master problem exactly. The algorithm uses different strategies for stabilizing the column generation process. Furthermore, the column generation method is employed within a branch-and-price procedure for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances. The results are compared with computational results obtained from a branch-and-bound procedure based on Lagrangean relaxation and subgradient optimization and a branch-and-bound method that uses the LP relaxation and polyhedral cuts

Keywords: Column Generation; Master Problem; Master Program; Restricted Master Problem; Subgradient Optimization (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:lnechp:978-3-642-17020-1_1

Ordering information: This item can be ordered from
http://www.springer.com/9783642170201

DOI: 10.1007/978-3-642-17020-1_1

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().