WikiMPRI

Teacher in charge: Sylvain Soliman (Inria)

The aim of this course is to introduce the concepts, principles and formalisms underlying constraint programming. The course will start from logical foundations and go up to recent extensions including concurrency and imperative features, while browsing through constraint logic programming and its applications to solving hard combinatorial problems.

A simple programming project (like SUDOKU solving) and a written exam will be used for grading the students.

• Logical foundations of constraint programming and of constraint solving problems (CSP).
• Examples of constraint logic programs for solving combinatorial problems.
• Constraint solving algorithms, simplification.
• Constraint propagation algorithms, variables' domain reduction.
• Global constraints, graph properties.
• Symmetries (variables, values, and both), and their elimination.
• Operational and fixpoint semantics of constraint logic programs (CLP).
• Protocol verification in CLP.
• Concurrent constraint languages (CC); operational and denotational semantics.
• Linear logic semantics; constraint systems for imperative features and modules.

Basics about operational semantics (rewriting rules and inference rules) and a certain taste for programming are required for this course.

Having attended the first year courses on PROLOG and constraint logic programming and on Programming languages semantics can be useful. The Abstract interpretation foundations or the corresponding M2 course can also reveal interesting.

Related courses : 2-1 2-4 2-5 2-6 2-7-1 2-31-1

The classes will be given in French by default.

Slides will be in English and available in PDF.

• Principles of Constraint Programming, Krzysztof Apt, Cambridge University Press, 2003.
• Programmation Logique par Contraintes, François Fages, Collection “Cours de l'Ecole Polytechnique” Ellipses, Paris, 1996.