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

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.