Constraint Satisfaction

Course Code : IA366

Total Hours : 18 hours

Time Periods : not available yet

Lecturers :

Christian Bessiere, Research Director, bessiere[at]lirmm.fr

Objectives

This module presents foundations of constraint programming (CP) and of the satisfaction of Boolean formulae (SAT). The most important algorithmic aspects are analyzed, together with complexity issues. The question of modeling a combinatorial problem as a constraint program is also addressed.

Acquired skills

Ability to model and solve a combinatorial problem with SAT and cconstraint techniques. Theoretical background to start doing research in that field.

Contents

Basic definitions, search algorithms, constraint propagation, local consistencies, polynomial classes, heuristics for exploring the search space, constraint solvers, global constraints, modeling. SAT, algorithm DPLL, efficient implementations, nogood learning, resolution.

References

  • Constraint processing, R. Dechter, Elsevier Morgan Kaufmann, 2003.
  • Handbook of constraint programming, Editors : P. van Beek, F. Rossi, and T. Walsh, Elsevier, 2006.