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 23.04.2020
  • lecture: siehe "Sonstiges"

Exam

All statements pertaining to examination modalities (for the summer/winter term of 2020) are given with reservations. Changes due to new requirements from the university will be announced as soon as possible.
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

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

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.

  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 10)

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

Register to the lectures via https://moodle.ruhr-uni-bochum.de/

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 a theoretic task of 12 points each. Additionally, there are 4 programming tasks with 10 points each. This course is passed once you collect 30 points from the theoretic tasks and 20 points from the programming tasks.