Foundations of Constraint Satisfaction
An introductory course on NASSLLI 2003, June 17-21, 2003, Indiana University, Bloomington, U.S.A.

Home | Author | Lectures | Resources

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.

Dr. Roman Barták

© 2003 Roman Barták