Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem |
| |
Affiliation: | 1. Research Group Logistics, Hasselt University, Agoralaan Gebouw D, 3590 Diepenbeek, Belgium;2. Research Foundation Flanders (FWO), Egmontstraat 5, 1000 Brussels, Belgium;3. CORMSIS Centre of Operational Research, Management Sciences and Information Systems, University of Southampton, Southampton, SO17 1BJ, UK |
| |
Abstract: | There appear to be two versions of the Dual Bin Packing problem in the literature. In addition, one of the versions has a counterpart in the cutting stock literature, known as the Skiving Stock Problem. This paper outlines branch-and-price algorithms for both. We introduce combinatorial upper bounds and well-performing heuristics from the literature in the branch-and-price framework. Extensive computational tests indicate that the branch-and-price approach is superior to the existing branch-and-bound procedures, based on combinatorial bounds. The tests illustrate the influence of different problem characteristics on the computation time and the limits of the branch-and-price approach. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|