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 15.04.2021
  • lecture Thursdays: from 08:30 to 10.00 o'clock
  • tutorial Fridays: from 14:00 to 14.45 o'clock

Exam

Die Angaben zu den Prüfungsmodalitäten (im WiSe 2020/2021 | SoSe 2021) erfolgen vorbehaltlich der aktuellen Situation. Notwendige Änderungen aufgrund universitärer Vorgaben werden zeitnah bekanntgegeben.
Form of exam:schriftlich + studienbegleitend
Registration for exam:Directly with the lecturer
continual assessment
description of exam:

Es wird 4 Aufgabenblätter mit jeweils theoretischen Teilaufgaben mit insgesamt 15 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 will be 4 exercise sheets each with theoretical subtasks with a total of 15 points and an additional 4 programming exercises with 10 points each. The examination is completed when 30 points are achieved in the theoretical tasks and 20 points in the programming tasks.