The displayed memo is not the latest version. Show (latest version).
Headings denoted with an asterisk ( * ) is retrieved from the course syllabus version Spring 2019
Content and learning outcomes
Course contents
Theory and methods:
The simplex method and interior point methods for linear programming. Utlization of problem structure, e.g., decomposition and column generation. Stochastic programming, methods and utilization of problem structure. Branch-and-bound methods for integer programming. Lagrangian relaxation and subgradient methods for integer programming problems with special structure.
Projects:
This part of the course consists of modeling practical optimization problems and using available optimization software to solve them. The projects are carried out in small groups. An important aspect of the course is cooperation within the group as well as presentations in talking and in writing.
Intended learning outcomes
The overall goal of the course is on the one hand that the student should master models, methods and theory for different forms of linear optimization and integer linear optimization, on the other hand that the student should be able to model and by a suitable modeling language solve realistic optimization problems, as well as presenting the results orally and in writing.
Upon completion of the course the student should be able to:
Explain how the simplex method works.
Explain how primal-dual interior methods for linear programming problems work.
From a problem description formulate a linear programming problem or an integer linear programming problem and solve it using the modeling language used in the course
Interpret the solutions of the real problems by fundamental concepts such as sensitivity analysis.
Explain how branch-and-bound works for solving integer programming problems.
Given suitable assumptions show fundamental results of linear programming such as strong duality and existence of extreme point solutions.
Explain what relaxation is.
Relate the modeling to the student's own field of research.
Students who have acquired deeper knowledge of the course are in addition expected to:
Use problem structure to solve special classes of linear programming problems, for example Dantzig-Wolfe decomposition.
Explain how Lagrangian relaxation can be used when solving integer linear programming problems.
Explain how the subgradient method works applied to dual problems associated with integer linear programs.
Use column generation for solving special classes of linear programs.
Use stochastic programming for modeling uncertainty in problem data.
More information
The course SF3812 is a PhD level version of the course SF2812.
PRO1 - Project work, 3.0 credits, Grading scale: P, F
TEN1 - Written exam, 4.5 credits, Grading scale: P, F
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
The section below is not retrieved from the course syllabus:
Project work ( PRO1 )
Written exam ( TEN1 )
Other requirements for final grade
Projects.
Written examination.
Ethical approach
All members of a group are responsible for the group's work.
In any assessment, every student shall honestly disclose any help received and sources used.
In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.