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