Constraint Technology

for Solving Combinatorial Problems

http://user.it.uu.se/~pierref/courses/CT/

Constraint technology is a collective term for a set of methods and tools for solving combinatorial problems. Such problems arise in many application domains, such as scheduling, planning, design, molecular biology, transport, logistics, and so on. Many companies are successfully deploying constraint technology, making knowledge thereof a useful asset on the job market. This course combines the theoretical and algorithmic foundations with the practical modelling and solving of real-life combinatorial problems.

**Lecture 1: Introduction**

What is a constraint? What kind of (real-life) problems can be modelled with constraints? With what contributing technologies are constraints processed? Domain declarations. Some basic comparison and arithmetic constraints. The*alldifferent*global constraint. Basic modelling issues.

(Slides, part 1) (Slides, part 2) (Programs) (Read Chapters 1 and 2 of the textbook) (Do Exercises 2.1, 2.4, 2.7, and 2.8 of the textbook)**Lecture 2: Constraint Processing in a Nutshell**

Equivalence of problems. Preprocessing. Propagation. Splitting. Search. Heuristics. Backtracking. Branch and bound.

(Slides) (Read Chapter 3 of the textbook) (No exercises)**Lecture 3: Consistency**

Bounds, arc, and path consistency. Higher levels of consistency.

(Slides) (Exercises) (Read Chapter 5 of the textbook)**Lecture 4: Constraint Propagation**

Propagation. Overview of a typical constraint kernel.

(Slides) (Read Chapter 7 of the textbook)**Lecture 5: Search**

Search strategies. General and problem-specific search heuristics. Meta-heuristics. Examples.

(Slides) (Exercises) (Read Chapter 8 of the textbook)**Lecture 6: Modelling**

Issues. Reified constraints. Higher-order constraints. Redundant decision variables and channelling constraints. Matrix modelling. Relational modelling. Examples.

(Slides & Exercises) (Programs) (Read Chapter 9 of the textbook)**Lecture 7: Modelling (continued)**

Implied and redundant constraints. Symmetry-breaking by adding constraints before search. Symmetry-breaking during search. Symmetry detection and introduction. Over-constrained problems. Examples.**Lecture 8: Global Constraints**

Overview. Revisiting the*alldifferent*global constraint. Some counting global constraints. Examples.

(Slides) (Exercises)**Lecture 9: Global Constraints (continued)**

Details. Examples.

(Slides & Exercises)**Lecture 10: Resource Scheduling Constraints**

Disjunctive, cumulative, and assignment+disjunctive approaches. Examples.

(Slides & Exercises)**Lecture 11: Routing, Geometric, and Regulation Constraints**

*Circuit*,*cycle*,*disjoint2*,*sequence*,*stretch*, etc. Examples.

(Slides & Exercises)**Lecture 12: Filtering Algorithms**

Main issues. Examples.

(Slides & Exercises)**Lecture 13: Optimisation Constraints**

Global cardinality with costs. Assignment with costs. Sum of weights of distinct values. Examples.

(Slides & Exercises)**Lecture 14: Tractability & Conclusion**

(Slides, part 1) (Slides, part 2) (Read Section 5.10 of the textbook)

40 points in science, technology, systems science, or linguistics, including 8 points in programming and basic algebra.

So the target audience includes third-year and fourth-yearundergraduatestudents.

Graduatestudents are of course also highly welcome; our expectations will just be higher.

- Pierre Flener, PhD, senior lecturer, docent
at Uppsala University, IT Department, MIC, room 1-336

Web: http://user.it.uu.se/~pierref/, Email: Pierre.Flener at it.uu.se

- Justin Pearson, PhD, senior lecturer
at Uppsala University, IT Department, MIC, room 1-441

Web: http://user.it.uu.se/~justin/, Email: Justin.Pearson at it.uu.se - Guest lecturers from SICS

Krzysztof R. Apt:

Principles of Constraint Programming.

Cambridge University Press, 2003.

Additional reading:

- The original paper on the alldifferent global constraint
- A recent tutorial by Nicolas Beldiceanu on global constraints (in French)

- CLP(FD) (a SICStus Prolog library): Manual, installed on the Solaris computers of the IT dept
- FaCiLe (an OCaml library): OCaml Book, FaCiLe manual [pdf], FaCiLe manual [ps], installed on the Solaris computers of the IT dept
- OPL: trial version installed on the computers in labs 1-312 and 1-313

- ASTRA research group on constraint technology, at Uppsala University
- SweConsNet, the Network for Sweden-based researchers and practitioners of Constraint technology
- Constraint Technology resources of the ASTRA group

All lectures take place in room 1-111 at Polacksbacken:Odd-numbered lectures are from 10:15 to 12:00, and even-numbered lectures are from 13:15 to 15:00.

- Tuesday 3 June 2003: Lectures 1 and 2
- Wednesday 4 June 2003: Lectures 3 and 4
- Tuesday 10 June 2003: Lectures 5 and 6
- Wednesday 11 June 2003: Lectures 7 and 8
- Monday 18 August 2003: Lectures 9 and 10
- Tuesday 19 August 2003: Lectures 11 and 12
- Monday 25 August 2003: Lectures 13 and 14

*Optional***exercises**are given at the end of most lectures. Solving them is highly recommended! On the Fridays immediately following lectures, the course**assistant**Magnus Ågren discusses solutions to some of these exercises in*optional***lessons**from 10:15 to 12:00 in room 1-111 at Polacksbacken.- A
*mandatory***project**, taking 2 weeks of work, is to be done. Choose a problem, for instance in CSPlib, as well as a programming language (see above), and contact us for our approval. Write several combinations of models and search procedures for the chosen problem, and empirically compare their performances, in running time and in the number of backtracks, for several problem instances. Especially experiment with redundant decision variables and implied constraints, and try to break any symmetries. Unless you have our permission, projects are to be done individually. Report to us a URL to a directory with a self-contained report (in PDF or PS) and documented programs and instance data used in your experiments. Late project proposals and reports are of course accepted; the grading turnaround may just be slower. A*pass grade*or a*fail grade*is given to each project report.

- The
**exam**took place on Sat 30 Aug 2003.

The**re-exam**is on Tue 13 Jan 2004, from 08:00 to 13:00, in building 5 of MIC.

Exam study guidelines.

Old exam: August 2003 (revised version). - The
**5 credit points**will be awarded upon passing*both*the exam and the mandatory project, using the passing grade (G or VG) earned on the exam.

- For
**graduate students**, the exam may be replaced by an additional or bigger project and a presentation thereon, without particular deadlines: contact us for arrangements.

Last modified: Fri 28 Nov 17:31:26 MEST 2003