zbMATH — the first resource for mathematics

A constraint for bin packing. (English) Zbl 1152.68586
Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 648-662 (2004).
Summary: We introduce a constraint for one-dimensional bin packing. This constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constraint can significantly reduce search on bin packing problems. We also demonstrate that when coupled with a standard bin packing search strategy, our constraint can be a competitive alternative to established operations research bin packing algorithms.
For the entire collection see [Zbl 1139.68008].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI