Constraint satisfaction and constraint propagation

An ubiquitous problem in many areas like decision-making or engineering is to find correct values for a set of variables which are subject to some constraints. Such problems, which are called constraint satisfaction problems (CSPs), are typically challenging to solve. The talk will start by a brief, non-technical overview of the techniques which have been proposed for several types of constraints.

I will next discuss more specifically one of these techniques, namely constraint propagation. Propagation uses the constraints of the problem to reduce the solution space of search algorithms. It has proved to be a flexible notion which can be adapted to most types of constraints. I will describe how it applies to boolean, finite-domain, numerical, and quantified constraints. I will also discuss a number of variants of propagation, like interval propagation, strong consistency methods and distributed propagation.

The last part of the talk will discuss applications of these methods and perspectives. Areas where propagation is widely used include planning and program verification, while more prospective areas of application are game theory and cryptanalysis. An important perspective for improving the efficiency of constraint solvers is solver cooperation, which aims at making several techniques work together.