Constraint Technology
for Solving Combinatorial Problems

Goals

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.

Contents

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

Prerequisites

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-year undergraduate students.
Graduate students are of course also highly welcome; our expectations will just be higher.

Instructors

• 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

Textbook

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)

Recommended Constraint Programming Languages / Libraries

• 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

References

• 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

Lecture Schedule

All lectures take place in room 1-111 at Polacksbacken:

• 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

Odd-numbered lectures are from 10:15 to 12:00, and even-numbered lectures are from 13:15 to 15:00.

Project, Assistant, Exercises, and Lessons

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

Exams & Grading

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