CM - Modelling for Combinatorial Optimisation (5 credits)
This PhD course was given once, in winter 2014/15, but is now also given as an undergraduate course (course 1DL449, 5 credits): autumn 2015 instance; the next instance will be in period 2 of autumn 2016.
The goal of this course is to learn the use of tools to solve hard combinatorial optimisation problems by first modelling them in a solver-technology-independent constraint-based modelling language and then using an off-the-shelf constraint solver, as opposed to designing an (approximation) algorithm from first principles.
Combinatorial optimisation problems arise in many fields, for example design and resource allocation in communication systems, motion planning for autonomous vehicles, verification and synthesis of chip circuits, scheduling of scientific experiments, design of cryptographic substitution functions, design of steel mill slabs, and identification of a minimum set of reactions to synthesise a given molecule.
In order to pass, the student must be able to:
- model a combinatorial problem using a solver-independent constraint-based modelling language;
- discuss various models of a combinatorial problem expressed in a constraint-based modelling language;
- describe and compare different constraint solving technologies that can be used by the back-end solvers to a constraint-based modelling language, including constraint programming (CP), local search (LS), Boolean satisfiability (SAT), SAT modulo theories (SMT), and integer linear programming (IP);
- decide which constraint solving technologies to try first when facing a new combinatorial problem, and motivate this decision;
- design and evaluate different models of a combinatorial problem for various constraint solving technologies.
The course covers:
- combinatorial (satisfaction or optimisation) problems,
- a constraint-based modelling language,
- the main characteristics of various constraint solving technologies,
- heuristics and good practice in modelling and solving combinatorial problems,
- examples of applications of combinatorial problem solving.
The theory and algorithms underlying the constraint solvers used in this course are not explained in depth, as specialised courses may exist for this purpose (such as course 1DL441 for CP), hence the course is also relevant for students in many research areas outside the IT department, especially nowadays that combinatorial problems become more and more central to many activities. The modelling and analytical skills that are central to this course are also important on their own, and can be applied to other types of problems.
The course is largely orthogonal to the course Combinatorial Optimisation using Constraint Programming (1DL441), where constraint programming (CP) technology is explained in detail, plus some of constraint-based local search (CBLS). Similarly, any course covering local search (LS), Boolean satisfiability (SAT and SMT), or integer linear programming (IP) will be largely orthogonal to this course.
The course consisted of a series of lectures, several personal assignments, and a personal project.
The schedule of the lectures was as follows in 2015/16. The lectures took place on Fridays from 10.15 to 12.00.
|5 December||2446||Lecture 1||Introduction||Jean-Noël|
|12 December||1212||Lecture 2||MiniZinc||Jean-Noël|
|16 January||1212||Lecture 3||Solving Technologies||Jean-Noël|
|15 January||4306||Lecture 4||Constraints||Pierre|
|23 January||1245||Lecture 5||Modelling (for CP) 1||Pierre|
|30 January||1245||Lecture 6||Modelling (for CP) 2||Pierre|
|6 February||1245||Lecture 7||Inference & Search in CP||Jean-Noël and Pierre|
|13 February||1245||Lecture 8||Symmetry||Pierre|
|20 February||1245||Lecture 9||Modelling for IP||Justin|
|27 February||1245||Lecture 10||Modelling for LS||Jean-Noël|
|6 March||1245||Lecture 11||Invited Lecture: A Use Case||Mats Carlsson (SICS)|
|20 March||1245||Lecture 12||Modelling for SAT and SMT||Jean-Noël|
Many thanks to Guido Tack of Monash University (Australia) and the MiniZinc team at NICTA for letting us use some of his slides: since they are copyrighted, they are password protected so that only UU students and employees can retrieve them.
There were two assignments during the course. They involved modelling and solving problems using the MiniZinc language and backend solvers of several technologies.
Students were encouraged to pick a personal project of their own interest but we also provided several subjects. As coming up with a good subject may be difficult, we encouraged students to discuss early on with the instructors in order to find or refine ideas.