Program > By speacker > Hebrard Emmanuel

I will first introduce, and give a viewpoint on, constraint propagation. Then, I will show through examples the multiple forms that this key aspect of constraint programming can take, from greedy approximations to exponential algorithms.

A complex combinatorial problem can always be seen as the conjunction of more primitive relations or subproblems. These subproblems range from constant time solvable relations to NP-complete problems such as Hitting Set or Max Clique. In constraint programming, these subproblems are referred to as constraints, irrespective of their complexities.

The existence of a solution for each individual constraint does not entail the existence of a solution of the composite problem. As a consequence, knowing how to solve efficiently each constraint is not sufficient.

Constraint propagation is the mechanism that connects the different reasonings done on each constraint. Rather than solving a constraint, the key idea is to consider the dual task of its reduction by removal of inconsistent solutions. Such reductions remain correct globally and can therefore be propagated to other constraints.

Typically, a propagation algorithm achieves domain consistency, that is, remove all inconsistent values from domains, in polynomial time. However, this is not set in stone. Weaker or stronger properties can be targeted, and we do not necessarily have to be complete for a given property. Examples illustrating these possibilities will be drawn from constraints linked to matching, hitting set and sequencing.