Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/91039
Author(s): Cristina Ribeiro
Maria Antónia Carravilla
Title: A global constraint for nesting problems
Issue Date: 2004
Abstract: Nesting problems are particularly hard combinatorial problems. They involve the positioning of a set of small arbitrarily-shaped pieces on a large stretch of material, without overlapping them. The problem constraints are bidimensional in nature and have to be imposed on each pair of pieces. This all-to-all pattern results in a quadratic number of constraints.Constraint programming has been proven applicable to this category of problems, particularly in what concerns exploring them to optimality.But it is not easy to get effective propagation of the bidimensional constraints represented via finite-domain variables. It is also not easy to achieve incrementality in the search for an improved solution: an available bound on the solution is not effective until very late in the positioning process.In the sequel of work on positioning non-convex polygonal pieces using a CLP model, this work is aimed at improving the expressiveness of constraints for this kind of problems and the effectiveness of their resolution using global constraints.A global constraint outside for the non-overlapping constraints at the core of nesting problems has been developed using the constraint programming interface provided by Sicstus Prolog. The global constrainthas been applied together with a specialized backtracking mechanism to the resolution of instances of the problem where optimization by Integer Programming techniques is not considered viable.The use of a global constraint for nesting problems is also regarded as a first step in the direction of integrating Integer Programming techniques within a Constraint Programming model.
Subject: Investigação operacional, Informática
Operations research, Informatics
URI: https://repositorio-aberto.up.pt/handle/10216/91039
Source: Integration of AI and OR Techniques in Constraint Programmimg for Combinatorial Optimization Problems
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: restrictedAccess
Appears in Collections:FEUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
54538.pdf
  Restricted Access
149.61 kBAdobe PDF    Request a copy from the Author(s)


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.