Project Description
Constraint programming has become the method of choice for modeling and solving combinatorial optimization problems such as planning of personnel and resources, computing time tables, packing and placement problems.
The success of constraint programming is based on the fact that it allows to simultaneously use several powerful propagation algorithms. The 'glue' for simultaneously using algorithms has not seen much advance. As a result, the strength of the used algorithms might be compromised, the overall efficiency might be poor, and modeling becomes more and more difficult with the advent of ever new and more powerful algorithms.
We will investigate how to truly coordinate constraint propagation in constraint programming systems. This will lead to stronger and more efficient constraint propagation and will simplify using constraint programming. We will devise coordination mechanisms for the glue. These mechanisms will be based on maintaining properties of the used algorithms and coordinating the execution of the algorithms on information computed from these properties.
Given the ever increasing number of powerful algorithms becoming available, the project will help that constraint programming continues to be the method of choice for solving hard combinatorial optimization problems in the future.
The project has been funded by the Swedish Research Council (VR) under grant 621-2004-4953, 2005–2007. Volume: 1875 KSEK, role: principal investigator.
Project Results
Results of the research conducted are contained in the following papers:
- Modeling Irregular Shape Placement Problems with Regular Constraints,
.
First Workshop on Bin Packing and Placement Constraints BPPC'08. - Efficient Constraint Propagation Engines,
.
Transactions on Programming Languages and Systems, 2008. - Advisors for Incremental Propagation,
.
Thirteenth International Conference on Principles and Practice of Constraint Programming, 2007. - Generating Propagators for Finite Set Constraints,
.
Twelfth International Conference on Principles and Practice of Constraint Programming, 2006. - Finite Domain Constraint Programming Systems,
.
Handbook of Constraint Programming, 2006. - Views and Iterators for Generic Constraint Implementations,
.
Recent Advances in Constraints (2005), 2006. - Views and Iterators for Generic Constraint Implementations,
.
Eleventh International Conference on Principles and Practice of Constraint Programming, 2005.
These results have been implemented in the Gecode constraint programming system. Gecode and hence the implemented results are widely used in research and education as well as by companies.