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 depthfirst 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 depthfirst search and we show how
to solve the problems where all the constraints cannot be satisfied
together  so called overconstrained problems.
Dr. Roman Barták
