Course Syllabus for

Linear and Combinatorial Optimization
Linjär och kombinatorisk optimering

FMAP05F, 7.5 credits

Valid from: Autumn 2022
Decided by: Maria Sandsten
Date of establishment: 2022-11-23

General Information

Division: Mathematics
Course type: Course given jointly for second and third cycle
The course is also given at second-cycle level with course code: FMAP05
Teaching language: English


In science, technology and economics, linear and combinatorial optimization problems appear more and more often. The most well known example is linear programming, where the so called simplex method has been of utmost importance in industry since it was invented in the middle of the 20th century. Other important problems, e.g. for effective data processing, contain discrete variables, for example integers. In connection with these, the importance of combinatorial methods has grown. The aim of the course is to make the PhD students aware of some problems in linear and combinatorial optimization which are important in applications, and to give them knowledge about modern mathematical methods for their solution. The aim is also to make the PhD student develop their ability to solve problems, with and without the use of a computer, and their ability to read mathematical texts.


Knowledge and Understanding

For a passing grade the doctoral student must

Competences and Skills

For a passing grade the doctoral student must

Course Contents

Linear programming. Integer programming. Transport problems. Assignment problems. Maximal flow. Some modern methods in combinatorial optimization. Algorithm complexity.

Course Literature

Kolman, B. & Beck, R.E.: Elementary Linear Programming with Applications. Academic Press, 1995, ISBN: 0-12-417910. Available as E-book from the Maths Library. Supplementary material. B.Korte & J. Vygen: Combinatorial Optimization, Theory and Algorithms. Springer, 2019, ISBN: 9783662585665. Sixth edition. An earlier edition is available as e-book from the Mathematics Library.

Instruction Details

Types of instruction: Lectures, seminars

Examination Details

Examination format: Written assignments. Assignments.
Grading scale: Failed, pass

Admission Details

Assumed prior knowledge: FMAB20 Linear Algebra. Programming with Python or Matlab. Some course in mathematics beyond calculus in several variables (for mathematical maturity).

Course Occasion Information

Contact and Other Information

Course coordinators:
Web page:

Complete view