Syllabus
1. Introduction: history and relation to other research areas, application areas, definition of a Constraint Satisfaction Problem and binary problems.
2. Local search techniques: hill climbing, min-conflicts, random walk, Tabu Search, GSAT, Genet.
3. Tree search techniques: backtracking, backjumping, dynamic backtracking, backmarking, limited discrepancy search, incomplete search.
4. Consistency techniques; node, arc, and path consistencies and algorithms to achieve them, general consistency notions.
5. Combining constraint propagation and search: forward checking, (partial/full) look ahead, variable and value ordering heuristics, backtrack-free search.
6. Optimization problems, branch and bound. Over-constrained problems and their models.
7. Global constraints.
8. Modelling problems and constraint programming in practice.
Annotation
The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency).
Solving over-constrained problems is also discussed as well as some modeling techniques are covered. Basic knowledge of programming language Prolog is expected.