*Principles of Constraint Programming*

by Krzystof Apt

(available in the library)

Slides used in the past years are made available below:

- Introduction
- CP in a Nutshell
- Complete Constraint Solvers
- Local Consistency
- Incomplete Constraint Solvers
- Constraint propagation
- Search

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

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

*13.10.11—Lecture 1*Introduction 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.

- Before the next session, revise the material presented and try the Exercise list 1.

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

- Before the next session, revise the material presented and try the Exercise list 2.

*25.10.11—Tutorial 1/Lecture 3*Tutorial: 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.

- Before the next session (tutorial) have a look at the Gauss-Jordan and Gauss methods for equations (they might be familiar to you).The Exercise list 3 is available.

*03.11.11—Tutorial 2/Lecture 5*Tutorial: 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 6*Gauss 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.

- Before the next session complete the Exercise List 3. Moreover Exercise list 4 is available.

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

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

*8.12.11—Lecture 6*Techniques 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 7*Techniques 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).

- Before the next session revise all material. Moreover, Exercise List 5 is available.

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

*05.01.12—Lecture 8*Incomplete 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 9*Constraint 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

- Before the next session revise all material.

*13.01.12—Lecture 10 and Tutorial 6*Constraint 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.

- Before the next session please revise all material. The Exercise List 6 is available.

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

- In principle, all what has been covered and is listed in Lectures and Topics.
- Modality of exam:
**written examination**. All written materials are allowed, no electronic devices. Id card and TUD registration card are necessary. - Exam: 7 February 2012, starting at 10:00am, duration 120 min, room E5 (and E6 should E5 not be sufficient).

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 @)