Discrete optimization
About
The course gives an introduction to modelling various optimization problems using linear programming (LP) and integer linear programming (ILP). The Simplex algorithm to solve LPs is described and analysed. The LP relaxations of ILPs are studied and analysed to design approximation algorithms. The duality theory of linear programs is studied and used to design approximation algorithms. Vector programs to model discrete optimization problems are described and relaxed to semi-definite programs (SDPs).
Prerequisites and selection
Entry requirements
- 7,5 credits programming in high level language like Java, Python etc
- 7,5 credits basic course in calculus/analysis
- 7,5 credits basic course in linear algebra
Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.
Selection
Selection is based upon the number of credits from previous university studies, maximum 285 credits
