## 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

• #### Buffered Resource Constraint: Algorithms and Complexity

Christian Bessiere, Emmanuel Hebrard, Marc-Andre Menard, Claude-Guy Quimper and Toby Walsh

• #### An Optimal Arc Consistency Algorithm for a Particular Case of Sequence Constraint

Mohamed Siala, Emmanuel Hebrard, and Marie-Jose Huguet

• #### An Optimal Arc Consistency Algorithm for a Chain of Atmost Constraints with Cardinality

Mohamed Siala, Emmanuel Hebrard and Marie-Jose Huguet

• #### Soft Constraints of Difference and Equality

Emmanuel Hebrard, Daniel Marx, Barry O'Sullivan and Igor Razgon

• #### 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

• #### Constraints of Difference and Equality: A Complete Taxonomic Characterisation

Emmanuel Hebrard, Daniel Marx, Barry O'Sullivan and Igor Razgon

• #### A Soft Constraint of Equality: Complexity and Approximability

Emmanuel Hebrard, Barry O'Sullivan and Igor Razgon

• #### Slide: A Useful Special Case of the Cardpath Constraint

Slide: A Useful Special Case of the Cardpath Constraint

• #### Distance Constraints in Constraint Satisfaction

Emmanuel Hebrard, Barry O'Sullivan and Toby Walsh

• #### Filtering Algorithms for the NValue Constraint

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh

• #### The ROOTS constraint

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh

• #### The RANGE Constraint: Algorithms and implementation

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh

• #### Filtering Algorithms for the NValue Constraint

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan and Toby Walsh

• #### Disjoint, Partition and Intersection Constraints for Set and Multiset Variables

Christian Bessiere, Emmanuel Hebrard, Brahim Hnich and Toby Walsh