Article ID: | iaor2007240 |
Country: | Netherlands |
Volume: | 170 |
Issue: | 2 |
Start Page Number: | 416 |
End Page Number: | 439 |
Publication Date: | Apr 2006 |
Journal: | European Journal of Operational Research |
Authors: | Degraeve Zeger, Peeters Marc |
Keywords: | programming: branch and bound |
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.