Lower bounds for the capacitated facility location problem based on column generation - Andreas Klose; Andreas Drexl (Universität Kiel, Institut für Betriebswirtschaftslehre; ZBW – Leibniz Information Centre for Economics, 2001)
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.
Keywords: 650; Capacitated Facility Location Problem; Integer Programming; Lagrangean Relaxation; Column Generation; Betriebliche Standortwahl; Mathematische Optimierung; Theorie