Syllabus for Modelling for Combinatorial Optimisation

Modellering för kombinatorisk optimering

A revised version of the syllabus is available.

Syllabus

  • 5 credits
  • Course code: 1DL448
  • Education cycle: Second cycle
  • Main field(s) of study and in-depth level: Computer Science A1N, Technology A1N
  • Grading system: Fail (U), Pass (3), Pass with credit (4), Pass with distinction (5)
  • Established: 2017-03-09
  • Established by: The Faculty Board of Science and Technology
  • Applies from: week 30, 2017
  • Entry requirements: 120 credits including Basic Course in Mathematics, Algebra I, and 10 credits in computer programming or another combination of courses containing basic concepts in algebra, combinatorics, logic, graph theory, set theory and implementation of (basic) search algorithms.
  • Responsible department: Department of Information Technology

Learning outcomes

In order to pass, the student must be able to:

  • model a combinatorial problem using a solver-independent constraint modelling language
  • discuss various models of a combinatorial problem expressed in a constraint modelling language
  • describe and compare different constraint solving techniques that can be used by the back-end solvers to a constraint modelling language, including constraint programming, local search, Boolean satisfiability (modulo theories), and integer programming
  • 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 techniques.

Content

The course focuses on modelling optimisation problems. The models can then be used to solve problems using an off-the-shelf solver.
The use of tools to solve hard combinatorial optimisation problems by first modelling them in a solver-independent constraint modelling language and then using an off-the-shelf constraint solver to solve them. Combinatorial (satisfaction or optimisation) problems, a constraint modelling language, the main characteristics of various constraint solving techniques, heuristics and good practice in modelling and solving combinatorial problems, examples of applications of combinatorial problem solving.

Instruction

Lectures, help sessions and solution sessions.

Assessment

Oral and written assignment presentations.

Syllabus Revisions

Reading list

Reading list

Applies from: week 30, 2017

The course does not have a course book.