 A branch & bound algorithm for cutting and packing irregularly shaped piecesR. Alvarez-Valdes, A. Martinez and J.M. Tamarit International Journal of Production Economics, 2013, vol. 145, issue 2, 463-477 Abstract: Cutting and packing problems involving irregular shapes, usually known as Nesting Problems, are common in industries ranging from clothing and footwear to furniture and shipbuilding. Research publications on these problems are relatively scarce compared with other cutting and packing problems with rectangular shapes, and are focused mostly on heuristic approaches. In this paper we make a systematic study of the problem and develop an exact Branch & Bound Algorithm. The initial existing mixed integer formulations are reviewed, tested and used as a starting point to develop a new and more efficient formulation. We also study several branching strategies, lower bounds and procedures for fixing variables, reducing the size of the problem to be solved at each node. An extensive computational study allows us first to determine the best strategies to be used in the Branch & Bound Algorithm and then to explore its performance and limits. The results show that the algorithm is able to solve instances of up to 16 pieces to optimality. Keywords: Cutting & packing; Nesting; Integer formulation; Branch & bound (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:proeco:v:145:y:2013:i:2:p:463-477 DOI: 10.1016/j.ijpe.2013.04.007 Access Statistics for this article International Journal of Production Economics is currently edited by Stefan Minner More articles in International Journal of Production Economics 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.