A branch & bound algorithm for cutting and packing irregularly shaped pieces

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.