A generalization of column generation to accelerate convergence

作者：Liang Dong; Wilhelm Wilbert E^*

来源：Mathematical Programming, 2010, 122(2): 349-378.

DOI：10.1007/s10107-008-0251-8

• Dantzig-Wolfe decomposition
• Column generation
• Linear program
• Integer program
• Multi-commodity network flow
• Cutting stock problem
• Production-assembly-distribution system design

This paper proposes a generalization of column generation, reformulating the master problem with fewer variables at the expense of adding more constraints; the sub-problem structure does not change. It shows both analytically and computationally that the reformulation promotes faster convergence to an optimal solution in application to a linear program and to the relaxation of an integer program at each node in the branch-and-bound tree. Further, it shows that this reformulation subsumes and generalizes prior approaches that have been shown to improve the rate of convergence in special cases.

• 出版日期2010-4