Department of Information Technology

CP - Combinatorial Optimisation using Constraint Programming (course 1DL441) - Autumn 2015

News

All announcements about the course will be made here, so check this page regularly:

  • The last lecture, on Fri 11 Dec, is cancelled.
  • Everyone is expected to attend the invited lecture Validated Numerics (CP over continuous domains) by Warwick Tucker of the Department of Mathematics at UU on Mon 30 Nov. It starts at 10:15 and spans the whole lecture slot.
  • 2015-10-06: Assignment 3 is published. All the necessary material (topics 1 to 9) will normally have been taught long before the deadline, and you can start even now.
  • 2015-10-01: Project part 3 is published. All the necessary material (topic 5) has already been taught.

Information

Official

  • Catalogue entry for this course, including the official course goals; unofficial secondary course goals are the acquisition of technical writing & typesetting skills as well as note-taking skills

Aim

Constraint programming proposes a set of techniques and tools for efficiently solving (hard) combinatorial problems. Doing so is crucial in many application domains, such as scheduling, planning, molecular biology, finance, linguistics, and so on. Many companies are successfully deploying constraint programming, making knowledge thereof a marketable asset. This course combines coverage of theoretical foundations with hands-on experience in modelling and solving real-life combinatorial problems.

The course is largely orthogonal to the course Modelling for Combinatorial Optimisation (1DL449), where a constraint-based modelling language (not a constraint programming language) is used to model combinatorial problems. The models are then processed by constraint solvers of various technologies, namely constraint programming (CP), constraint-based local search (CBLS), Boolean satisfiability (SAT), SAT modulo theories (SMT), and integer programming (IP), whereas in this course only a solver of a CP technology is used and the other technologies are just mentioned. None of the five technologies is explained in algorithmic detail, so that the problem modelling is done mostly in black-box fashion, whereas in this course, CP technology is explained in white-box fashion, so that the student can also make contributions to the technology itself.

See the articles Constraint Programming in Sweden, Constraint Technology and the Commercial World (these links work from the UU network), and Constraint Programming -- The Paradigm to Watch, for instance.

Target Group

Natural-science students (biology, bioinformatics, physics, chemistry, ...), mathematics students, engineering students, finance students, linguistics students, computer-science students, and anyone interested in solving complex problems that have many constraints. Note that constraint programming is complementary to linear programming (a common technique in operations research): this course will be of particular interest to students with such a background. The target audience includes third-year and fourth-year undergraduate students, as well as graduate students.

Prerequisites

120 higher-education credits (that is 120 ECTS points) in science, technology, systems science, or linguistics, including 12 higher-education credits (that is 12 ECTS points) in programming and basic algebra. Programming skills in C++ are assumed.

Updated  2015-12-07 14:13:10 by Pierre Flener.