NDLI: A global constraint for nesting problems

Content Provider	Springer Nature Link
Author	Ribeiro, Cristina Carravilla, Maria Antónia
Copyright Year	2009
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 constraint has 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.
Starting Page	99
Ending Page	118
Page Count	20
File Format	PDF
ISSN	02692821
Journal	Artificial Intelligence Review
Volume Number	30
Issue Number	1-4
e-ISSN	15737462
Language	English
Publisher	Springer Netherlands
Publisher Date	2009-10-24
Publisher Place	Dordrecht
Access Restriction	Subscribed
Subject Keyword	Nesting Constraint programming Global constraints Computer Science Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Linguistics and Language

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A robot decision making framework using constraint programming

Logic programming for combinatorial problems

When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems : A short Exposition of the concept

An Arc-Consistency Algorithm for Dynamic and Distributed Constraint Satisfaction Problems

Solution Techniques for Constraint Satisfaction Problems: Foundations

Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches

Expressive Applications of Constraint Logic Programming

Finding robust solutions for constraint satisfaction problems with discrete and ordered domains by coverings

Towards Fast Vickrey Pricing using Constraint Programming

A global constraint for nesting problems

Similar Documents

A robot decision making framework using constraint programming

Logic programming for combinatorial problems

When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems : A short Exposition of the concept

An Arc-Consistency Algorithm for Dynamic and Distributed Constraint Satisfaction Problems

Solution Techniques for Constraint Satisfaction Problems: Foundations

Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches

Expressive Applications of Constraint Logic Programming

Finding robust solutions for constraint satisfaction problems with discrete and ordered domains by coverings

Towards Fast Vickrey Pricing using Constraint Programming

A global constraint for nesting problems