Stabilized Branch-and-Price Algorithms for Vector Packing Problems
Katrin Heßler (),
Timo Gschwind () and
Stefan Irnich ()
Additional contact information
Katrin Heßler: Johannes Gutenberg-University Mainz, Germany
Timo Gschwind: Johannes Gutenberg-University Mainz, Germany
Stefan Irnich: Johannes Gutenberg-University Mainz, Germany
No 1713, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dualoptimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, bounded, or unbounded depending on the speciﬁc master problem formulation. Its fast resolution is decisive for the overall performance of the branch-and-price algorithm. In order to provide a generic but still efficient solution approach for the subproblem, we formulate it as a shortest path problem with resource constraints (SPPRC), yielding the following advantages: (i) Violated dual-optimal inequalities can be identiﬁed as a by-product of the SPPRC labeling approach and thus be added dynamically; (ii) branching decisions can be implemented into the subproblem without deteriorating its resolution process; and (iii) larger instances of higher-dimensional VPPs can be tackled with branch-and-price for the ﬁrst time. Extensive computational results show that our branch-and-price algorithms are capable of solving VPP benchmark instances effectively.
Keywords: Cutting; Vector packing; Shortest path problem with resource constraints; Dual-optimal inequalities; Stabilization (search for similar items in EconPapers)
Pages: 25 pages
New Economics Papers: this item is included in nep-cmp
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_1713.pdf First version, 2017 (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:1713
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 ().