Course Code : IA366
Total Hours : 18 hours
Time Periods : not available yet
Christian Bessiere, Research Director, bessiere[at]lirmm.fr
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.
Ability to model and solve a combinatorial problem with SAT and cconstraint techniques. Theoretical background to start doing research in that field.
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.
- Constraint processing, R. Dechter, Elsevier Morgan Kaufmann, 2003.
- Handbook of constraint programming, Editors : P. van Beek, F. Rossi, and T. Walsh, Elsevier, 2006.