Foundations of Constraint Programming

1References

Principles of Constraint Programming
by Krzystof Apt
(available in the library)

Slides used in the past years are made available below:

  1. Introduction
  2. CP in a Nutshell
  3. Complete Constraint Solvers
  4. Local Consistency
  5. Incomplete Constraint Solvers
  6. Constraint propagation
  7. Search

Although there will be no laboratory sessions, you might appreciate experimenting some exercises with Eclipse-Prolog

2News

IMPORTANT: STUDENTS THAT ARE NOT ENROLLED IN EMCL/CL SHALL FORMALLY CONTACT THE EXAMINATION OFFICE TO NOTIFY ME THE PROCEDURE FOR LETTING YOU PARTICIPATE IN THE EXAM.

Exam: 7 February 2012, starting at 10:00am, duration 120 min, room E5 (and E6 should E5 not be sufficient).

The course terminated on 26/1/2012. No lectures/tutorials are planned before the exam.

Extra session on Fri 13/1 at DS1.

Tutorials will usually be scheduled on even calendar weeks.

An extra tutorial is planned on 20/12/2011 at DS4.
Christmas break: last day of teaching period is 21/12/2011, lectures resume on 4/1/2012


25/10 DS4 a lecture is planned and the lecture on 10/11 is cancelled
3/11: The tutorial will be held by Amin

3Course Info

Lectures and topics

13.10.11—Lecture 1Introduction to the course; presentation based on the slides 1, introducing the notion of constraint, constraint satisfaction problem, constraint optimisation problems, and illustrating several examples of applications.

20.10.11—Lecture 2(Presentation based on the slides 2). Definitions of projection, Equivalence of CSPs, equivalence wrt a set. Notions of solved and failed CSPs. Preprocessing, criterion for termination, atomicity and splitting, heuristics, effects of splitting and search techniques (Backtracking, branch&bound). Constraint propagation. Examples of domain reductions on boolean constraints and on integer intervals.

25.10.11—Tutorial 1/Lecture 3Tutorial: discussion on the list 1 (Ex 1: the guinea pig is a pigeon! Ex 2: Do we need two or three values in the domain?). Lecture: (Continuation of slides 2) --Interval arithmetics, examples of applications in CSP, restriction of the domains (rules for multiplication). Presentation based on the slides 3: initial concepts until page 7.

27.10.11—Lecture 4(Presentation based on the slides 3, up to page 19) --Rules and proof systems, Rules application, derivation, solved/failed/stabilising CSP problems; example of solved/failed/stabilising derivation. Terms and unification; unification as a CSP. Representation of reals as terms.

03.11.11—Tutorial 2/Lecture 5Tutorial: discussion on the list 2 and solutions. Lecture: (Continuation of slides 3, pp 20-25) --Normal Form, Pivot Form, Lin Proof System, Gauss Jordan Elimination Method. (Both sessions held by Amin).

17.11.11—Lecture 6Gauss Elimination method and comparison with Gauss Jordan's one. Techniques for local consistency (based on slide n. 4, until p.13): generalities and motivation; node consistency, arc-consistency, hyper-arc consistency, direct arc consistency and relations with consistency, through examples.

24.11.11—Tutorial 3Correction of List 3 of exercises (up to 3.3 included).

1.12.11—Tutorial 4Completion of correction of List 3, List 4 and discussions.

8.12.11—Lecture 6Techniques for local consistency (continuation until p 27): normalised CSP, path consistency, direct path consistency, k-consistency, strong k-consistency (definitions properties and examples).

15.12.11—Lecture 7Techniques for local consistency (completion of group of slides 4): Representing a CSP as a graph,width of a graph, relating directional arc consistency and directional path consistency to graph representations; further generalisation to relational (i,m)-consistency (definitions, theorems, examples).

20.12.11—Tutorial 5Correction of List 5, up to 5.2 included, and discussions.

05.01.12—Lecture 8Incomplete Constraint Solvers (presentation based on the batch 5 of slides). Problems and motivations, equality and disequality constraints, boolean constraints, linear constraints on integer intervals and integer finite domains, arithmetic constraints over integer intervals. Sketchy presentation of the problems to consider when dealing with arithmetic constraints on reals. We have followed in detail the presentation until page 24 included, and mentioned how extending some techniques presented for the integer case to accomodate the reals will generate further questions we will need to address.

12.01.12—Lecture 9Constraint Propagation (presentation based on the batch 6 of slides, up to page 22 included). Motivations, constraint propagation for local consistency; mathematical background: partial orderings, some properties of functions (monotonicity,inflationarity,idempotency, commutative and semi-commutative application of functions), fix-points and least fix-points, notion of stablisation of a function; Iteration algorithms (Direct Iteration, Simple Iteration, Generic Iteration, and their generalisations to compound domains) and their properties (termination and fix-points) when applied to partial ordering and functions on them with specific algebraic properties; how to relate the Abstract Framework to Constraint Propagation

13.01.12—Lecture 10 and Tutorial 6Constraint Propagation (continuation and completion of the batch 6 of slides). Local consistency notions in the abstract framework: node consistency + direct iteration, arc consistency + compound domain (ARC algorithm-direct iteration), hyper-arc consistency + compound domain; the use of generic iteration for other notions of local consistency and for incomplete constraint solvers.
Correction of the remaining exercises in the List 5 and discussions.

19.01.12—Lecture 11 Search (batch 7 of slides, up to p.34 included) Motivations. Definition and examples of search trees, labeling trees, reduced labeling trees without constraint propagation; labeling trees with constraint propagation (prop labeling trees); considerations on the size of the produced trees with and without constraint propagation;Instances of prop labeling trees: forward checking,partial look ahead, full look ahead; Examples of the instances on an n-queen problem; search algorithms with/out backtrack with/out constraint propagation.

26.01.12—Tutorial 7 Correction of the Exercise list 6. This was the last session, the course is now over.

Material covered and to be prepared for the exam

4Tutors and Office Hours

Amin Timany will help in the organisation of the course. The Open house slot is a good venue for discussing your questions, and hopefully I can answer them. Otherwise just drop me an email and we'll arrange for an appointment.

27.01.12Paola Bruscoliemail (replace AT by @)