Go to:
Logótipo
Comuta visibilidade da coluna esquerda
Você está em: Start > Publications > View > A Global Constraint for Nesting Problems
Publication

Publications

A Global Constraint for Nesting Problems

Title
A Global Constraint for Nesting Problems
Type
Article in International Scientific Journal
Year
2008
Authors
Cristina Ribeiro
(Author)
FEUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Journal
Vol. 30 No. 1-4
Pages: 99-118
ISSN: 0269-2821
Publisher: Springer Nature
Indexing
Publicação em ISI Web of Science ISI Web of Science
COMPENDEX
INSPEC
Scientific classification
FOS: Engineering and technology > Other engineering and technologies
CORDIS: Physical sciences > Computer science
Other information
Authenticus ID: P-003-TBA
Abstract (EN): 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.
Language: English
Type (Professor's evaluation): Scientific
Contact: mcr@fe.up.pt
Documents
We could not find any documents associated to the publication.
Related Publications

Of the same authors

Planeamento agregado da produção em CLP (1999)
Technical Report
Maria Antónia Carravilla; Maria Cristina Ribeiro
Demand uncertainty for the location-routing problem with two-dimensional loading constraints (2016)
Chapter or Part of a Book
de Queiroz, TA; José Fernando Oliveira; José Fernando Oliveira; Maria Antónia Carravilla; Maria Antónia Carravilla; Miyazawa, FK; Miyazawa, FK
A MIP model for production planning in the roasting coffee industry (2016)
Chapter or Part of a Book
Ospina, DY; Maria Antónia Carravilla; Maria Antónia Carravilla; José Fernando Oliveira; José Fernando Oliveira
The Dotted-Board Model: A new MIP model for nesting irregular shapes (2013)
Article in International Scientific Journal
Franklina M B Toledo; Maria Antonia Carravilla; Cristina Ribeiro; Jose F Oliveira; Miguel M Gomes

See all (15)

Of the same scientific areas

Curso Intensivo de Photoshop (2000)
Technical Report
Vítor Manuel Ferreira Alves Carvalho
Simulating communication in a service-oriented architecture for V2V networks (2009)
Article in International Conference Proceedings Book
Edgar F. Esteves; Eugénio Oliveira; Rosaldo J. F. Rossetti; João F. B. Goncalves
Modeling of an Optimized Multilayer Cover Design for a Uranium Mill Tailings Disposal (2011)
Article in International Conference Proceedings Book
Maria de Lurdes Dinis; António Fiúza
XML applications and associated technologies = XML aplicações e tecnologias associadas (2008)
National Conference Proceedings Book
José Carlos Ramalho; João António Correia Lopes; Salvador Abreu

Of the same journal

On the joint-effect of class imbalance and overlap: a critical review (2022)
Another Publication in an International Scientific Journal
Santos, MS; Pedro Henriques Abreu; Japkowicz, N; Fernandez, A; Carlos Soares; Wilk, S; Santos, J
Unlabeled learning algorithms and operations: overview and future trends in defense sector (2024)
Article in International Scientific Journal
Oliveira, EE; Rodrigues, M; Pereira, JP; António Mendes Lopes; Mestric, II; Bjelogrlic, S
Tensor decomposition for analysing time-evolving social networks: an overview (2021)
Article in International Scientific Journal
Fernandes, S; Fanaee T, H; João Gama
Novelty detection in data streams (2016)
Article in International Scientific Journal
Faria, ER; Goncalves, IJCR; de Carvalho, ACPLF; João Gama
Artificial intelligence, cyber-threats and Industry 4.0: challenges and opportunities (2021)
Article in International Scientific Journal
Becue, A; Praca, I; João Gama

See all (9)

Recommend this page Top
Copyright 1996-2025 © Faculdade de Direito da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z
Page created on: 2025-07-10 at 11:12:34 | Privacy Policy | Personal Data Protection Policy | Whistleblowing