Optimal rectangle packing: New results

We present new results on the problem of finding an enclos-ing rectangle of minimum area that will contain a given a set of rectangles. Many simple scheduling tasks can be mod-elled by this NP-complete problem. We present a new lower bound on the amount of wasted space in a partial solution, a new dominance condition that prunes many partial solutions, and extend our algorithms to packing unoriented rectangles. For our experiments, we consider the set of squares of size 1x1, 2x2,...,NxN, and find the smallest rectangle that can con-tain them for a given value of N. While previously we solved this problem up to N=22, we extend this to N=25. Overall, our new program is over an order of magnitude faster than our previous program running on the same machine. We also show that for the larger problems, our optimal algorithm is faster than one that finds the best slicing solution, a popular approximation algorithm. In addition, we solve an open prob-lem dating to 1966, concerning packing the set of consecutive squares up to 24x24 in a square of size 70x70