Skip to main content

Summer 2020

Operations Research

Sommersemester 2020, 6CP
03-BB-699.01

Moderne betriebliche Informationssysteme nutzen verschiedene quantitative Verfahren aus der Informatik und Mathematik um Planungs- und Entscheidungsprozesse zu unterstützen. So lassen sich viele praktische Fragestellungen als (ganzzahlige) lineare Optimierungsprobleme formulieren: z.B. Warenfluss und Planung von Produktionsprozessen in der Logistik, Portfoliotheorie und Risikomanagement in der Finanzwelt sowie Netzwerkdesign und Routing in der Telekommunikation.

Die Vorlesung gibt eine Einführung in die grundlegenden Methoden der linearen und ganzzahligen linearen Optimierung. Themen sind: Mathematische Modellierung praktischer Fragestellungen (Entscheidungs-, Planungs- und Optimierungsprobleme), Struktur und Geometrie linearer Programme, Simplexverfahren, Komplexität, Dualität, Sensitivitätsanalyse; Methoden zum Lösen ganzzahliger linearer Probleme: Branch-and Bound Methode, Schnittebenen-Verfahren, Dynamische Programmierung und Greedy Verfahren; gundlegende kombinatorische Algorithmen für Graphen- und Netzwerkflussprobleme.

Dozentin:  Prof. Dr. Nicole Megow
Assistent:  Franziska Eberle

Literatur:

  • [W] Winston, A.: Operations Research, Algorithms and Applications, Whiley & Sons, Duxbury Press, 2003.
  • [NSW] Nickel, Stein, Waldmann: Operations Research, Springer Gabler, 2. Auflage, 2014.
  • [DDKS] Domschke, W.; Drexl, A.; Klein, R.; Scholl, A.: Einführung in Operations Research, 5. Auflage, Springer, 2015.
  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.

Algorithms and Uncertainty

Master Course in Summer 2020
03-ME-602.99c, 6 ETCS points

Description:

A key assumption of all basic algorithm design classes is that all the data is fully accessible at the start of the computation.

However, from the point of view of many real-world applications of computer science (such as the stock market, cloud scheduling, network design), this assumption is simply not true. In the above examples, our knowledge of the current data is only partial or based on historical estimates.

The class Algorithms and Uncertainty will teach students about the most common models of such uncertain data and how to design and analyze efficient algorithms in these models.

Specifically, we will cover the theory of online algorithms, where the input arrives without any prior information (such as network packets arriving to a router) and also needs to be processed immediately, before the next piece of input arrives. This model is best suited for analyzing critical networking and scheduling systems where devices and algorithms must perform well even in the worst-case scenario.

In the cases where previous history can be used to model the upcoming data, we often employ stochastic optimization. There, the algorithms work with the assumption that data is drawn from some probability distribution known ahead of time.

Nowadays, another source of information is often available: machine learning algorithms can generate predictions which are accurate most of the time. However, there is no guarantee on the quality of the prediction, as the current instance may not be covered by the training set. This statement motivated a very recent research domain that will be covered in this course: how to use untrusted predictions in order to improve guaranteed algorithms.

The course will be taught in English. The course is accessible to any student with basic algorithm classes and basic knowledge of graph theory.

Lecturers:
Dr. Martin Böhm
Prof. Dr. Nicole Megow
Dr. Bertrand Simon

Stud-IP Link: Algorithms and Uncertainty

First lecture: Lecture times and location will be specified in April (The summer semester starts on April 14.)