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