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.