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 automatonbased 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 nonsolutions as possible, since these nonsolutions 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

Buffered Resource Constraint: Algorithms and Complexity
Christian Bessiere, Emmanuel Hebrard, MarcAndre Menard, ClaudeGuy Quimper and Toby Walsh
CPAIOR

An Optimal Arc Consistency Algorithm for a Particular Case of Sequence Constraint
Mohamed Siala, Emmanuel Hebrard, and MarieJose Huguet
Constraints

An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality
Mohamed Siala, Emmanuel Hebrard and MarieJose Huguet
CP

Soft Constraints of Difference and Equality
Emmanuel Hebrard, Daniel Marx, Barry O'Sullivan and Igor Razgon
JAIR

Range and Roots: Two Common Patterns for Specifying and Propagating Counting and Occurrence Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh
AIJ

Constraints of Difference and Equality: A Complete Taxonomic Characterisation
Emmanuel Hebrard, Daniel Marx, Barry O'Sullivan and Igor Razgon
CP

A Soft Constraint of Equality: Complexity and Approximability
Emmanuel Hebrard, Barry O'Sullivan and Igor Razgon
CP

Slide: A Useful Special Case of the Cardpath Constraint
Slide: A Useful Special Case of the Cardpath Constraint
ECAI

Distance Constraints in Constraint Satisfaction
Emmanuel Hebrard, Barry O'Sullivan and Toby Walsh
IJCAI

Filtering Algorithms for the NValue Constraint
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh
Constraints

The ROOTS constraint
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh
CP

The RANGE Constraint: Algorithms and implementation
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh
CPAIOR

Filtering Algorithms for the NValue Constraint
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh
CPAIOR

Disjoint, Partition and Intersection Constraints for Set and Multiset Variables
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich and Toby Walsh
CP