Foundations of Constraint Programming
A tutorial on ETAPS2003, April 12, 2003, Warshaw, Poland

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

© 2003 Roman Barták