Constraint Propagation

The main focus of my research is on developing constraint propagation algorithms for specific global constraints. In a nutshell, a global constraint is nothing else than a combinatorial problem. The Global Constraint Catalog provides a automaton-based characterisation of a very large list of global constraints.
Even though a global constraint can be seen as any other combinatorial problem, the key difference is that we do not actually want to solve it since the solution we would find has no garantee (and an extremely small likelihood) to be extendable to other constraints of the larger problem.
Therefore, we solve instead the dual problem. We try to eliminate as many non-solutions as possible, since these non-solutions cannot be part of an overall solution. The way we eliminate those solutions depends on the type of structure we use to represent the potential search space. We generally want to find the minimal relaxation with respect to this structure. Most often we use finite discrete domains, and in this case the minimal relaxation will be called Arc Consistency. In other cases we consider domains defined as discrete intervals, and this corresponds to Bounds Consistency.

Here are the slides of the tutorial on this topic that I gave at ROADEF 2014. This presentation is based on some of the following papers:

Publications on Constraint Propagation Algorithms