We consider the two-dimensional rectangular strip packing problem. We
first consider a simple but effective approach to speed up exhaustive
search for perfect packings based on dynamic programming.

We then introduce and demonstrate the effectiveness of BLD*, a new
stochastic search variation of the bottom-left decreasing (BLD)
heuristic. The BLD heuristic successively places the rectangles as
far down and to the left as possible in decreasing order of height,
width, area, and perimeter; this has proven much more effective than
other heuristic approaches including simulated annealing and genetic
algorithms. The BLD* heuristic successively tries random orderings,
chosen from a distribution determined by their Kendall-tau distance
from one of these fixed orderings. Our experiments on benchmark and
randomly generated problems show that BLD* produces significantly
better packings than BLD after only 1 minute of computation. We
also extend our BLD* algorithm to the case where variable orientation
is allowed.

Finally, we observe that people seem able to reason about packing
problems extremely well. We incorporate our new algorithms in an
interactive system that combines the advantages of computer speed and
human reasoning. Using the interactive system, we are able to quickly
produce significantly better solutions than previous methods or BLD*
by itself.

Joint work with Neal Lesh and Joe Marks.