J.F.: Applying constraint logic programming to the resolution of nesting problems

Nesting problems are combinatorial optimisation problems where one or more pieces of material or space must be divided into smaller irregular pieces, minimising the waste. In OR, the state-of-the-art in nesting problems is to solve them by means of heuristic algorithms; the use of mixed integer programming models can handle only rather small instances. The satisfaction of geometric constraints is at the core of nesting problems. We propose here a CLP formulation of the problem that makes use of the geometric constraints generated by the use of nofit polygons. This approach reveals itself as very flexible with respect to the use of problem features for extra constraints and control of the search. Ongoing work involves comparing solutions obtained with CLP with both integer programming and heuristic approaches. 1 The nesting problem The nesting problem belongs to the more generic class of combinatorial optimization problems, the cutting and packing problems. In these problems, one or more pieces of material or space must be divided into smaller pieces. The objective is usually to minimize the waste, i.e. the portion of the big pieces that is not used to produce small pieces