####
New Interactive and Heuristic Approaches to 2D Rectangular Strip Packing

In this paper, we consider the two-dimensional rectangular strip
packing problem. This problem appears unamenable to standard
local search techniques, such as simulated annealing or genetic
algorithms. A standard simple heuristic, Bottom-Left-Decreasing (BLD), has
been shown to handily beat these more sophisticated search techniques.

We introduce and demonstrate the effectiveness of BLD*,
a stochastic search variation of BLD. While BLD places the rectangles in
decreasing order of height, width, area, and perimeter, BLD*
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.

Furthermore, 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 on
benchmark problems.