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

requirements

keine

recommended knowledge

Contents of the course: Mathematics I

materials

miscellaneous:

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.