Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities

被引：11

作者：

Gschwind, Timo ^{[1
]}

Irnich, Stefan ^{[1
]}

机构：

[1] Johannes Gutenberg Univ Mainz, Gutenberg Sch Management & Econ, Chair Logist Management, Jakob Welder Weg 9, D-55128 Mainz, Germany

来源：

OR SPECTRUM | 2017年 / 39卷 / 02期

关键词：

Column generation; Dual inequalities; Stabilization; OPTIMIZATION;

D O I：

10.1007/s00291-016-0463-x

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present two new methods to stabilize column-generation algorithms for the temporal knapsack problem (TKP). Caprara et al. (INFORMS J Comp 25(3):560-571, 2013] were the first to suggest the use of branch-and-price algorithms for Dantzig-Wolfe reformulations of the TKP. Herein, the respective pricing problems are smaller-sized TKP that can be solved with a general-purpose MIP solver or by dynamic programming. Our stabilization methods are tailored to the TKP as they use (deep) dual-optimal inequalities, that is, inequalities known to be fulfilled by all (at least some) optimal dual solutions to the linear relaxation. Extensive computational tests reveal that both new stabilization techniques are helpful. Several previously unsolved instances are now solved to proven optimality.

引用

页码：541 / 556

页数：16

共 21 条

[1]

[Anonymous], 1993, CONVEX ANAL MINIMIZA

[2]

[Anonymous], 2004, Knapsack Problems, DOI DOI 10.1007/978-3-540-24777-710

[3]

Bartlett M, 2005, LECT NOTES COMPUT SC, V3524, P34

[4] Dual-optimal inequalities for stabilized column generation [J].