Solving nesting problems with non-convex polygons by constraint logic programming

Solving nesting problems with non-convex polygons by constraint logic programming

0.00 Avg rating0 Votes
Article ID: iaor20042761
Country: United Kingdom
Volume: 10
Issue: 6
Start Page Number: 651
End Page Number: 663
Publication Date: Nov 2003
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: cutting stock, programming: mathematical
Abstract:

In this paper an application of constraint logic programming (CLP) to the resolution of nesting problems is presented. Nesting problems are a special case of the cutting and packing problem, in which the pieces generally have non-convex shapes. Because of their combinatorial optimization nature, nesting problems have traditionally been tackled by heuristics and in the recent past by meta-heuristics. When trying to formulate nesting problems as linear programming models, to achieve global optimal solutions, the difficulty of dealing with the disjunction of constraints arises. On the contrary, CLP deals easily with this type of relationships among constraints. A CLP implementation for the nesting problem is described for convex and non-convex shapes. The concept of nofit polygon is used to deal with the geometric constraints inherent to all cutting and packing problems. Computational results are presented.

Reviews

Required fields are marked *. Your email address will not be published.