zbMATH — the first resource for mathematics

An MDD approach to multidimensional bin packing. (English) Zbl 1382.68224
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 128-143 (2013).
Summary: We investigate the application of multivalued decision diagrams (MDDs) to multidimensional bin packing problems. In these problems, each bin has a multidimensional capacity and each item has an associated multidimensional size. We develop several MDD representations for this problem, and explore different MDD construction methods including a new heuristic-driven depth-first compilation scheme. We also derive MDD restrictions and relaxations, using a novel application of a clustering algorithm to identify approximate equivalence classes among MDD nodes. Our experimental results show that these techniques can significantly outperform current CP and MIP solvers.
For the entire collection see [Zbl 1263.68017].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P05 Data structures
90C27 Combinatorial optimization
Full Text: DOI