Stabilized Column Generation for the Temporal Knapsack Problem using Dual- Optimal Inequalities
Timo Gschwind () and
Stefan Irnich ()
Additional contact information
Timo Gschwind: Johannes Gutenberg-Universität Mainz, Germany
Stefan Irnich: Johannes Gutenberg-Universität Mainz, Germany
No 1413, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
We present two new methods to stabilize column-generation algorithms for the Temporal Knapsack Problem (TKP). Caprara et al. [Caprara A, Furini F, and Malaguti E (2013) Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem. INFORMS J. on Comp. 25(3):560–571] 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.
Keywords: Column generation; dual inequalities; stabilization (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp
Date: 2014-11-13, Revised 2014-11-13
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1413.pdf First version, 2014 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1413
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().