Exact Algorithms for the Two-Dimensional Strip Packing Problem with and without Rotations

Mitsutoshi Kenmochi, Takashi Imamichi, Koji Nonobe, Mutsunori Yagiura, Hiroshi Nagamochi
We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 degrees rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein 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 combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.

European Journal of Operational Research, 198 (2009) 73-83.

PDF file of the draft version (the same contents with the journal version but different layout)

See also the following technical report version, which contains computational results of the branch-and-bound algorithm based on sequence-pairs.
Back to the Paper List