course: Linear Optimization

teaching methods:
lecture with tutorials
responsible person:
Prof. Dr.-Ing. Aydin Sezgin
Prof. Dr.-Ing. Aydin Sezgin (ETIT), M. Sc. Alaa Alameer (ETIT)
offered in:
summer term

dates in summer term

  • start: Thursday the 11.04.2019
  • lecture Thursdays: from 08:30 to 10.00 o'clock in ID 04/471
  • lecture Thursdays: from 08:30 to 10.00 o'clock in ID 04/459
  • tutorial Fridays: from 12:30 to 14.00 o'clock in ID 04/471
  • tutorial Fridays: from 12:30 to 14.00 o'clock in ID 04/459


Form of exam:schriftlich + studienbegleitend
Registration for exam:FlexNow
continual assessment
description of exam:

Es wird 5 Aufgabenblätter mit jeweils theoretischen Teilaufgaben mit insgesamt 12 Punkten und zusätzlich 4 Programmieraufgaben zu je 10 Punkten geben. Die Prüfungsleistung ist erbracht, wenn bei den theoretischen Aufgaben 30 Punkte und bei den Programmieraufgaben 20 Punkte erreicht sind.


Many engineering (but also non-engineering) aspects require solutions to problems with objectives and constraints. Optimization is used as a systematic tool to efficiently solve these problems. Students of this course learn the central aspects of linear optimization, including: - modeling of information technology related problems (such as power allocation) and everyday life problems (such as knapsack problem, soduko, diet) - duality, as well as necessary and sufficient conditions - methods to help the efficient calculation of solutions


  1. Introduction and Overview
Motivation, formulation of linear problems, variants, examples, partly linear objective functions

Graphic description and solutions Linear algebra: Overview and notation 2. Geometry in Linear Optimization

System Message: ERROR/3 (<string>, line 7)

Unexpected indentation.
Convex sets, polyhedra, extremal points
  1. The Simplex-Method Conditions on optimality, development, implementation
  2. Duality Theory Motivation, dual problem, duality theorem
  3. Game Theory
  4. Sensitivity Analysis (local)
  5. Network Flow Problems Formulation, problems: shortest path/maximum flow, networks-simplex algorithm
  6. Interior Point Methods Affine scaling alogirthm
  7. Mixed Integer Linear Programming Formulation Methods: Branch and bound, cutting plane
  8. Applications



recommended knowledge

Contents of the course: Mathematics I




  1. Boyd, S., Vandenberghe, L. "Convex Optimization", Cambridge University Press, 2004


Additional literature: • Berstsimas, D., Tsitsikilis, J. N., “Introduction to linear optimization”, Athena Scientific, 1997 • Hamacher, H. W., Klamroth, K., “Lineare Optimierung und Netzwerkoptimierung”, 2. Auflage, Vieweg Verlag, 2006

Script for lecture: • Verfürth, R., “Optimierung”, Skriptum 2014 (¬

There are 5 homeworks with 3 theoretic tasks of 4 points each. Additionally, there are 3 programming tasks if 10 points each. This course is passed once you collect 30 points from the theoretic tasks and 15 points from the programming tasks.