Department of Information Technology

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.

Objective

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.

The PhD course was given by Jean-Noël Monette (coordinator), Pierre Flener, and Justin Pearson.

Learning Outcomes

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.

Content

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.

Schedule

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.

Date Room Activity Topic Lecturer
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.

Assignments

There were two assignments during the course. They involved modelling and solving problems using the MiniZinc language and backend solvers of several technologies.

Project

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.

Software and Resources

MiniZinc

We use MiniZinc, a medium-level constraint-based modelling language:

Interesting Links

  • Essence, another constraint modelling language

Sponsorship

This course was made possible thanks to postgraduate education grants from the Centre for Interdisciplinary Mathematics (CIM) and the Computing Science Division (CSD), both at Uppsala University.

Updated  2016-08-09 20:48:20 by Pierre Flener.