Applying constraint logic programming to the resolution of nesting problems

In nesting problems a two-dimensional piece of material must be divided into smaller pieces with irregular shape. The variant of the problem dealt with here considers only one big piece with fixed width and infinite length. Nesting problems have traditionally been tackled either by heuristic algorithms or, for rather small problems, by building mixed integer programming models. A more flexible approach is proposed using Constraint Logic Programming (CLP). An acceptable cutting pattern is naturally expressed via the constraints imposed on each pair of pieces therein, and the minimisation criterion is easily turned into a search strategy. The main advantage of a CLP formulation for the problems in this class is that it does not need to conform to a rigid model. It lends itself very naturally to the integration of the intrinsic features of the problem and to the use of heuristic methods for obtaining initial solutions.