Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem

Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem

0.00 Avg rating0 Votes
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: ,
Keywords: programming: branch and bound
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.

Reviews

Required fields are marked *. Your email address will not be published.