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
|