Multidimensional bin packing is a challenging combinatorial problem with applications to cloud computing, virtualized datacenters, and machine reassignment. In contrast to the classical bin packing model, item sizes and bin capacities both span a vector of values, requiring that feasible assignments honor capacity constraints across all dimensions. Recent work has yielded significant improvements over traditional CP and MIP encodings by incorporating multivalued decision diagrams (MDDs) into a heuristic-driven CSP-based search. In this paper, we consider a radically different approach to multidimensional bin packing, in which the complete contents of bins are considered sequentially and independently. Our algorithm remains depth-first, yet adopts a powerful least commitment strategy for items when their exclusion from a bin is attempted. We abandon the use of MDDs, and instead aggregate capacity over incomplete bins to establish significantly stronger bounds on the solution quality of a partial assignment. Empirical results demonstrate that our approach outperforms the state-of-the-art by up to four orders of magnitude, and can even solve some previously intractable problems within a fraction of a second.
展开▼
