The project is concerned with the formally correct and efficiently executable specification of constraint propagation for complex, global constraints by means of rules. A constraint satisfaction problem consists of a set of constraints which must be satisfied by every solution. Problems of this type, including NP-complete ones, can be solved well by problem simplification methods (constraint propagation) combined with search. Notably constraint-specific propagation methods can cause huge reductions of the search space at low cost, drastically reducing the solving time in turn.

Specification as well as correct implementation of such methods requires substantial expertise, however. Rules have proved to be a useful formalism for the description of the propagation of primitive, simple constraints.  Appropriate rule-based languages, notably Constraint Handling Rules, and corresponding implementations exist in which constraint propagation procedures can immediately be executed. Several methods for generating propagation rules automatically from declarative definitions of primitive constraints have been developed in the last years.

The purpose of this project is to investigate the specification of the propagation of global constraints by rules, and the automatic generation of rule-based constraint propagation mechanisms for such constraints. This project proposal pursues the classical ideal of generating practical programs from formal specifications.

See the research projects page for the project partners and further information.