Home |
Author | Schedule
| Resources
Constraint
programming is a technology for declarative description and solving
of hard combinatorial problems. The user just states the constraints
over the problem variables and the system finds a valuation of the
variables satisfying the constraints.
The tutorial
gives a survey of basic constraint satisfaction techniques. First,
the notion of a constraint is explained and some examples of practical
applications of constraint technology are given. Then we present
enumeration algorithms (search) for solving constraints, in particular
generate and test, backtracking, backjumping, dynamic backtracking,
backmarking, and discrepancy search and we compare their advantages
and weaknesses. In the next part we concentrate on consistency techniques;
we present the algorithms for arc and path consistency and we explain
the general notions of k-consistency, (i,j)-consistency, inverse
consistency, and singleton consistency. After that, we show how
consistency techniques are integrated with enumeration in forward
checking and look ahead methods and we present some techniques for
solving over-constrained problems. The tutorial is concluded with
an example of modelling a real-life problem using constraints.
The tutorial
is targeted to a broad computer science community, in particular
to everyone interested in techniques for solving hard combinatorial
problems (scheduling and assignment problems, circuit design, network
management and configuration, interactive graphics, molecular biology
etc.). No prior knowledge of Constraint Programming is required.
Dr. Roman Barták
|