 Exact algorithms for the two-dimensional strip packing problem with and without rotationsMitsutoshi Kenmochi, Takashi Imamichi, Koji Nonobe, Mutsunori Yagiura and Hiroshi Nagamochi European Journal of Operational Research, 2009, vol. 198, issue 1, 73-83 Abstract: We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 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. Keywords: Branch-and-bound; Combinatorial; optimization; Strip; packing; Rectangles; Two-dimension (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:198:y:2009:i:1:p:73-83 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.