Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Constraint Programming (24h, 3 ECTS)

Teacher in charge: Sylvain Soliman (Inria)

Goals

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.

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
11/09/17 Introduction to CLP, operational semantics, examples
18/09/17 CLP: fixpoint semantics
25/09/17 CLP logical semantics; CSP: solving by simplification and domain reduction
02/10/17 CLP: the Warren Abstract Machine; CSP: Symmetries
08/10/17 deadline for the programming project
09/10/17 CLP: typing; CHR; Programming project discussion
16/10/17 (no class)
23/10/17 (no class)
30/10/17 CC: examples, operational and denotational semantics
06/11/17 CC: linear logic semantics; LCC
13/11/17 LCC: logical semantics, links with CHR, typing and modules for CLP
20/11/17 exam 16.15-18.15
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA