A generalization of column generation to accelerate convergence

• 成果类型: Article
• 署名作者: Liang, Dong; Wilhelm, Wilbert E.
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0251-8
• 发表日期: 2010
• 页码: 349-378
• 关键词: multicommodity flow problems; knapsack-problem; time windows; DECOMPOSITION; algorithm

摘要

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.