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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2003

Autores

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

Revista

Título: International Transactions in Operational Research

Vol. 10 Nº 6

Páginas: 651-663

ISSN: 0969-6016

Editora: Wiley-Blackwell

Indexação

Scopus - 20 Citações

Classificação Científica

CORDIS: Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional

Outras Informações

ID Authenticus: 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.

Idioma: Português

Tipo (Avaliação Docente): Científica

Nº de páginas: 13