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:
- Everyone is strongly encouraged to attend the invited lecture by Mats Carlsson
of SICS
on handball tournament scheduling, to be given at the complementary course Modelling for Combinatorial Optimisation
on Mon 14 Dec from 15:15 to 17:00 in room 1145.
- 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.
- Everyone is expected to attend the invited lecture Task Sequencing for Dual-Arm Robot Assembly by Johan Ludde (Lundin) Wessén
of ABB Corporate Research (Västerås)
on Mon 23 Nov. It starts at 10:15 and may span 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
- Slightly technical advertisement
for this course
- 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
- Schedule
of this course instance
- Student Portal
of this course instance
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.