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

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.