Carnegie Mellon University
Browse

An MDD Approach to Multidimensional Bin Packing

Download (374.12 kB)
journal contribution
posted on 2008-12-01, 00:00 authored by Brian Kell, Willem-Jan Van HoeveWillem-Jan Van Hoeve

We investigate the application of multivalued decision dia- grams (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.

History

Publisher Statement

All Rights Reserved

Date

2008-12-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC