Combinatorial Optimization

Postgraduate course

Course description

Objectives and Content

Objectives: The course aims to give knowledge in theory and solution methods for combinatorial optimization

Content: The course deals with theory and algorithms for solving integer and combinatorial optimization problems. Topics that are covered include models and algorithms for network flow, matching, assignment, matroids, knapsack problems, relaxations, tree search methods, and cutting plane methods.

Learning Outcomes

On completion of the course the student should have the following learning outcomes defined in terms of knowledge, skills and general competence:


The student

  • knows the theory of combinatorial optimization problems


The student can

  • formualate a combinatorial optimization problem efficiently
  • model industrial planing problems in terms of combinatorial optimization

General competence

The student can

  • explain how fast a combinatorial optimization problem can be solved
  • explain the mathematical theory underlying algorithms for combinatorial optimization

ECTS Credits


Level of Study


Semester of Instruction

Required Previous Knowledge
Recommended Previous Knowledge
Credit Reduction due to Course Overlap
I273: 10 ECTS
Access to the Course
Access to the course requires admission to a programme of study at The Faculty of Mathematics and Natural Sciences
Teaching and learning methods

The teaching is given in terms of lectures and group sessions

Lectures / 4 hours per week

Group sessions/ 2 hours per week

Compulsory Assignments and Attendance
Two compulsory assignments, valid for one subsequent semester.
Forms of Assessment
Final oral exam.
Grading Scale
The grading scale used is A to F. Grade A is the highest passing grade in the grading scale, grade F is a fail.
Assessment Semester
Examination both spring semester and autumn semester. In semesters without teaching the examination will be arranged at the beginning of the semester.
Reading List
The reading list will be available within July 1st for the autumn semester and December 1st for the spring semester
Course Evaluation
The course will be evaluated by the students in accordance with the quality assurance system at UiB and the department
Examination Support Material
Programme Committee
The Programme Committee is responsible for the content, structure and quality of the study programme and courses.
Course Coordinator
Course coordinator and administrative contact person can be found on Mitt UiB, or contact mailto:studieveileder@ii.uib.noStudent adviser
Course Administrator
The Faculty of Mathematics and Natural Sciences represented by the Department of Informatics is the course administrator for the course and study programme.