Propagating the bin packing constraint using linear programming. (English)
Cohen, David (ed.), Principles and practice of constraint programming ‒ CP 2010. 16th international conference, CP 2010, St. Andrews, Scotland, September 6‒10, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15395-2/pbk). Lecture Notes in Computer Science 6308, 129-136 (2010).
Summary: The state-of-the-art global constraint for bin packing is due to Shaw. We compare two linear continuous relaxations of the bin packing problem, based on the DP-flow and Arc-flow models, with the filtering of the bin packing constraint. Our experiments show that we often obtain significant improvements in runtime. The DP-flow model is a novel formulation of the problem.
Start
Contact
Print
General Help
