Foundations of Constraint Satisfaction A foundational course on ESSLLI 2002, August 5-16, 2002, Trento, Italy

Home | Author | Lectures | Resources This course is targeted to everyone interested in solving real-life combinatorial problems using the techniques of constraint satisfaction. After attending the course, the attendees should have a broad view of constraint satisfaction techniques and detail knowledge of the fundamental solving algorithms. The course provides a deep and broad survey of algorithms for constraint satisfaction. A notion of constraint satisfaction problem (CSP) is defined and the methods for conversion to binary constraints are presented. Then we describe the local search techniques for solving CSP's, including the algorithms like hill climbing, min-conflicts, and tabu search. Systematic search algorithms are presented next, starting from chronological backtracking, continuing through conflict-directed backjumping and backmarking and concluding with the discrepancy based search. A significant part of the course is dedicated to the description of the consistency techniques (constraint propagation) for reducing the search space. We present the algorithms for node, arc and path consistency and explain the general notions of k-consistency, (i,j)-consistency, inverse consistency, and singleton consistency. We also show how the consistency techniques are combined with enumeration (search) in forward checking and look ahead methods. The course is concluded with the notes about solving optimisation and over-constrained problems. Dr. Roman Barták

© 2002 Roman Barták