Kaisa_2012_3_photo by Veikko Somerpuro

This courses provides knowledge on how to solve complex optimization problems via combinatorial and discrete optimization.

From cost-effective logistics and transport, resource-constrained production planning, better sustainability, and shift scheduling, to learning deep neural networks, optimising real-time markets and designing better treatments to life-threatening diseases, the ability to efficiently obtain good solutions to complex optimization optimization problems has a remarkable impact on individuals, societies, and the world.

This course is an introduction to combinatorial (discrete) optimization, providing an exposition of some of the most central concepts and algorithmic approaches to solving computationally hard optimization problems at large. The course provides background and tools for modelling and solving complex optimization problems via declarative means, in particular linear and mixed-integer programming, as well as local search. Both key mathematical concepts and practical declarative optimization systems are covered.

While the course aims to be relatively self-contained, basic background on fundamental algorithms, linear algebra, and practical programming are key assets for successful completion of the course.

Enrol
Moodle
Log in to view the registration key for Moodle.

Timetable

Here is the course’s teaching schedule. Check the description for possible other schedules.

DateTimeLocation
Mon 5.11.2018
12:15 - 14:00
Wed 7.11.2018
10:15 - 12:00
Mon 12.11.2018
12:15 - 14:00
Wed 14.11.2018
10:15 - 12:00
Mon 19.11.2018
12:15 - 14:00
Wed 21.11.2018
10:15 - 12:00
Mon 26.11.2018
12:15 - 14:00
Wed 28.11.2018
10:15 - 12:00
Mon 3.12.2018
12:15 - 14:00
Wed 5.12.2018
10:15 - 12:00
Mon 10.12.2018
12:15 - 14:00
Wed 12.12.2018
10:15 - 12:00

Description

Master's Programme in Computer Science is responsible for the course.

The course belongs to the Discrete Algorithms CSM12100 and Discrete Algorithms (elective) CSM22100 modules.

The course is available to students from other degree programmes.

CSM12101 Algorithm Design and Analysis

Courses in the Discrete Algorithms study module.

Provides prerequisite knowledge for CSM12106 Approximation algorithms.

Recommended further studies: Automated reasoning

Explains properties of and connection between decision, search, enumeration, and optimization problems. Gives examples of polynomial-time and NP-hard optimization problems. Describes distinctive characteristics of exhaustive and local search style optimization algorithms. Describes some tractable classes of NP hard optimization problems. Describes distinctive characteristics of different declarative NP optimization languages and algorithms for them. Simulates the Simplex algorithm for solving linear programming instances. Derives dual formulations of integer programs. Derives different integer programming relaxations and cutting planes. Explains integer programming duality. Simulates branch-and-bound and branch-and-cut search. Develops domain-specific branch-and-bound algorithms for different NP hard problems. Encodes NP optimization problems compactly using integer programs and declarative NP Boolean optimization languages. Applies declarative optimization solvers to solve instances of NP-hard optimization problems.

Recommended time/stage of studies for completion:

1st or 2nd year of MSc studies.
After CSM12101 Algorithm Design and Analysis.

Term/teaching period when the course will be offered:

Autumn term, period II, biannually (first time in Autumn 2018)

Combinatorial search spaces, polynomial-time and NP-hard optimization problems. Linear programming and integer programming. Integer linear programming duality and relaxations. Cutting planes. Branch-and-bound and branch-and-cut. Finite-domain constraint optimization, Boolean optimization, maximum satisfiability. Stochastic local search.

The course does not follow any textbook directly.

Lecture slides and tutorials. A list of recommended supplementary literature will be provided when the course begins.

The course activities may vary per instantiation of the course.

The core study material consists of online lecture materials. Weekly lectures present the core study material with additional explanation and examples. Active participation in the lectures by the students is encouraged to support learning.

Students are given exercise problems geared towards learning the knowledge and skills described in the learning outcomes. Students present their solutions in weekly tutorials either in person or in electronic form (as instructed in the individual exercise sheets) and discuss them with a teacher to obtain feedback. The exercise problems may range from theoretical problems to implementation-level tasks.

Homework assignments (passed), final grade based on final exam, grading scale 0-5.

Contact teaching consisting of 2x 2 h lectures and 1x 2 h tutorials weekly. Other forms of activities, such as programming tasks as homework, are also possible.

Completion requirements: homework and final exam.