Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
Management Science · 2005 · Volume 51 · Issue 11
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
Enable JavaScript for citation tools and additional paper interactions.