Optimal Vector Packing in Multiple Dimensions with Heuristic Search

We study an extension of the well-known bin-packing problem to multiple dimensions, resulting in the "vector packing" problem. The problem is to find the minimum number of multidimensional bins to pack a set of vectors into without exceeding the bin capacity in any dimension of any bin. While we use approximate methods to inform our search, we ultimately return optimal solutions. This work is an attempt to extend the results of [Kor03] to multiple dimensions and combine it with some new techniques. A hybrid DFBnB algorithm which searches in two separate problem spaces is used as the final algorithm. Our hybrid algorithm also uses a heuristic to assist the search, and an approximate algorithm to initially bound the cost of an optimal solution. The resulting algorithm can be run on vector-packing problems with any number of dimensions, and good results are shown for up to five-dimensional problems. An attempt is also made to define a method to compare these results with future algorithms, as consensus on appropriate test suites for vector-packing problems seems to be lacking