# course: Linear Optimization

number:
141219
teaching methods:
lecture with tutorials
responsible person:
Prof. Dr.-Ing. Aydin Sezgin
Lecturers:
Prof. Dr.-Ing. Aydin Sezgin (ETIT), M. Sc. Alaa Alameer (ETIT)
language:
german
HWS:
3
CP:
3
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

## Exam

 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.

## goals

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

## content

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

keine

## recommended knowledge

Contents of the course: Mathematics I

## literature

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

## miscellaneous

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 (http://www.ruhr-uni-bo¬chum.de/num1/skripten.html)

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.