Foundations of Constraint Satisfaction

Abstract:
Constraint programming is a technology for declarative description and solving of hard combinatorial problems. It
represents one of the closest approaches to the Holy Grail of automated problem solving: the user states the constraints
over the problem variables and the system finds a valuation of the variables satisfying the constraints. The course gives a
broad and deep survey of the major constraint satisfaction techniques.
First, the notion of a constraint is explained and some examples of practical applications of constraint technology
are given. Then we survey the basic search algorithms for solving constraints; both local search and depth-first search
methods are presented. The algorithms are explained in an incremental nature showing how the more advanced
algorithms are built up on improvements of the simpler algorithms. In the next part we concentrate on the core of
constraint satisfaction technology - consistency techniques. We explain the main consistency levels like arc and path
consistency and we present several algorithms how to achieve them. We also describe how the consistency techniques
reduce the search space in the depth-first search and we show how to solve the problems where all the constraints cannot
be satisfied together - so called over-constrained problems.

Outline:
1. Introduction and basic terminology. Local search techniques (hill-climbing, min-conflicts, random-walk, tabu-search).
2. Systematic search techniques: chronological backtracking, backjumping, backmarking, discrepancy search.
3. Introduction to consistency techniques: node consistency, arc consistency (AC1, AC3, AC4), directional arc
consistency.
4. Path consistency (PC1, PC2). Generic consistency notions: k-consistency, (i,j)-consistency, singleton consistency.
5. Integration of consistency with search, value/variable ordering. Optimisation and over-constrained problems. Final
notes.