Premium
Solving nesting problems with non‐convex polygons by constraint logic programming
Author(s) -
Carravilla M. A.,
Ribeiro C.,
Oliveira J. F.
Publication year - 2003
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00434
Subject(s) - nesting (process) , mathematical optimization , heuristics , regular polygon , polygon (computer graphics) , constraint programming , computer science , mathematics , constraint (computer aided design) , packing problems , stochastic programming , telecommunications , materials science , geometry , frame (networking) , metallurgy
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 problems, 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.