Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2007-005 (January 30, 2007)
Exact Algorithms for the 2-Dimensional Strip Packing Problem with and without Rotations
by Mitsutoshi Kenmochi, Takashi Imamichi, Koji Nnobe, Mutsunori Yagiura, Hiroshi Nagamochi
We examine various strategies for exact approaches to the 2-dimensional strip packing problem (2SP) with and without rotations of 90 degrees. We first develop a branch-and-bound algorithm based on the sequence pair representation.
Next, we focus on the perfect packing problem (PP), which is a special case of 2SP where all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A suitable combination of these rules yields very effective algorithms, especially for feasible instances of PP. We then propose several methods to apply the PP algorithms to the strip packing problem. We confirm through computational experiments that
the algorithm based on the sequence pair representation can solve instances of 2SP with only about 10 rectangles,
while the algorithm with a branching rule based on the staircase placement can solve benchmark instances of PP with 49 rectangles. Moreover, we confirm that our algorithms efficiently solve 2SP instances with up to 500 rectangles when optimal solutions have small wasted space.