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

• Type: Article in International Scientific Journal
• Date: 2003

Authors

M. A. Carravilla (Author) FEUP; C. Ribeiro (Author) FEUP; J. F. Oliveira (Author) FEUP

Journal

Title: International Transactions in Operational Research

Vol. 10 No. 6

Pages: 651-663

ISSN: 0969-6016

Publisher: Wiley-Blackwell

Indexing

Scopus - 20 Citations

Scientific classification

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research

Other information

Authenticus ID: P-00N-CTP

Abstract (EN): 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. Due to 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.

Language: Portuguese

Type (Professor's evaluation): Scientific

No. of pages: 13