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.
- M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura, H. Nagamochi,
Exact Algorithms for the 2-Dimensional Strip Packing Problem
with and without Rotations,
Technical Report 2007-005,
Department of Applied Mathematics and Physics,
Graduate School of Informatics,
the AMP site.
Back to the Paper List