| Summary: |
This project concerns the development and test of tools for solving nesting problems with Constraint Programming, and their benchmarking with respect to alternative approaches. The project is focused on two issues crucial for the efficient application of Constraint Programming to combinatorial problems: the use of global constraints and the definition of strategies for exploring the search space.
The team members are committed to an ongoing project (CLPNest, POSI/33757/SRI/2000, to be concluded in September 2002), where Constraint Logic Programming tools for nesting problems are being developed and tested on a prototype application. Another result of CLPNest is a collection of problems and the identification of useful heuristics for improving the search results. CLPNest has shown that CLP languages are a convenient modelling tool for combinatorial problems.
The nesting problem is a two-dimensional problem belonging to the more generic class of combinatorial optimisation problems, the cutting and packing problems. In this problem, a big piece must be divided into smaller irregular shaped pieces, minimizing the waste. This problem has a direct industrial relevance in all production processes where raw materials have to be cut into irregular parts (e.g. garment, footwear and furniture industries) as well as environmental implications, since the reduction of waste implies the usage of less raw material.
From an Operations Research (OR) point of view, constraint programming languages can be regarded as modelling languages with a rich set of primitive constraints and open with respect to the development of customized search strategies. The use of constraint programming in some combinatorial problems is made easy by the use of so-called global constraints. Global constraints capture the dependencies between variables in a problem and are offered as library functions.
Previous work by the team members has shown that the geometric constraints of the nesting pr  |
Summary
This project concerns the development and test of tools for solving nesting problems with Constraint Programming, and their benchmarking with respect to alternative approaches. The project is focused on two issues crucial for the efficient application of Constraint Programming to combinatorial problems: the use of global constraints and the definition of strategies for exploring the search space.
The team members are committed to an ongoing project (CLPNest, POSI/33757/SRI/2000, to be concluded in September 2002), where Constraint Logic Programming tools for nesting problems are being developed and tested on a prototype application. Another result of CLPNest is a collection of problems and the identification of useful heuristics for improving the search results. CLPNest has shown that CLP languages are a convenient modelling tool for combinatorial problems.
The nesting problem is a two-dimensional problem belonging to the more generic class of combinatorial optimisation problems, the cutting and packing problems. In this problem, a big piece must be divided into smaller irregular shaped pieces, minimizing the waste. This problem has a direct industrial relevance in all production processes where raw materials have to be cut into irregular parts (e.g. garment, footwear and furniture industries) as well as environmental implications, since the reduction of waste implies the usage of less raw material.
From an Operations Research (OR) point of view, constraint programming languages can be regarded as modelling languages with a rich set of primitive constraints and open with respect to the development of customized search strategies. The use of constraint programming in some combinatorial problems is made easy by the use of so-called global constraints. Global constraints capture the dependencies between variables in a problem and are offered as library functions.
Previous work by the team members has shown that the geometric constraints of the nesting problem are inefficiently captured by primitive constraints and there are no appropriate global constraints in existing CP systems. Exploratory work with global constraints for nesting has been started and the results are quite promising.
The project aims at contributing with efficient algorithms for handling nesting constraints. Equally important for obtaining good solutions is the development of efficient search strategies, and the heuristic methods proposed in CLPNest will be pursued and integrated in a common prototype application. The project results will be useful for the community working with nesting problems, providing a prototype application where new strategies for obtaining solutions can be added on top of a framework where the problem constraints are enforced. |