Constraint Programming

Outline

  • 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.

Prerequisites and related courses

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

Language and material

The classes will be given in French by default.

Slides will be in English and available in PDF.

Bibliography

  • 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.

Tentative Schedule

Date (DD/MM/YY) Content
15/09/15 Introduction to CLP, operational semantics, examples
22/09/15 CLP: fixpoint semantics
29/09/15 CLP logical semantics; CSP: solving by simplification and domain reduction
06/10/15 CLP: the Warren Abstract Machine; CSP: Symmetries
09/10/15 deadline for the programming project (no class)
13/10/15 CLP: typing; CHR; Programming project discussion
20/10/15 (no class)
27/10/15 (no class)
03/11/15 CC: examples, operational and denotational semantics
10/11/15 CC: linear logic semantics; LCC
17/11/15 LCC: logical semantics, links with CHR, typing and modules for CLP
24/11/15 exam 12.45-14.45