This module is taught in English. This module is regularly offered every winter term.

This course was previously offered in the winter terms 2021/2022, 2022/2023 and 2023/2024.

Link official module page

Description

Optimisation is the selection of a best element from a set of available alternatives. Such problems are fundamental in our daily lives and arise in all quantitative disciplines from computer science and engineering to operations research and economics.

The aim of this course is to show the methodology for solving constraint optimisation problems both for linear and non-linear problems. These methodologies are also known as Linear and Non-Linear Programming, respectively. Special attention is paid to the application of these methodologies in practical problems ranging from transportation to portfolio optimisation. We will study in-depth how to take a practical problem and formulate it into a mathematical formulation. Then we introduce algorithms for solving these. Finally, theoretical foundations are underlying these algorithms are addressed to train intuition on applicability.

Recommended prerequisites

We expect attendees to be proficient in the material from the following modules:

• Discrete algebraic structures
• Mathematics I
• Mathematics II

We further recommend basic knowledge of the following topics:

• Graphs and networks
• Probability theory (probability spaces, expected value)
• Programming in Python, C++, C# or Java

Topics

In this module we cover the following topics:

• modelling linear programming problems
• graphical method
• algebraic background
• convexity
• polyhedral theory
• simplex method
• degeneracy and convergence
• duality
• interior-point methods
• quadratic optimization
• integer linear programming

Setup

• Weekly lectures (in presence) and weekly tutorial session (in presence).
• Each week an assignment is handed out, which should be solved individually outside the classroom  and then be submitted for grading. The assignment and its solutions are then discussed in the subsequent tutorial session. If sufficiently many points are awarded in the grading process (cumulative over all assignments of the term), then a bonus is given for the final exam at the end of the term.
• Final exam (written) for 90 minutes at the end of the term, whose outcome (together with a potential bonus from the assignment) determines the final grade for the module.

Overall module load: 6 ECTS credit points

Recommended literature

• B. Guenin, J. Könemann, L. Tunçel: A gentle introduction to optimization. Cambridge University Press, 2014
• A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003
• B. Korte and T. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, 2018
• T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2013