Summer 2018

Grundlagen der linearen Optimierung

Vorlesung im Sommersemester 2018

Viele praktische Fragestellungen lassen sich als lineare Optimierungsprobleme formulieren, bspw. in der Logistik (Warenfluss und Planung von Produktionsprozessen) oder in der Finanzwelt (Portfoliotheorie und Risikomanagement). In einem linearen Optimierungsproblem sind sowohl die Zielfunktion als auch die Nebenbedingungen, die die Menge der zulässigen Lösungen beschreiben, linear. Die Vorlesung gibt eine Einführung in die Theorie und Praxis der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Vorlesungsthemen sind u.a.: Modellierung und Struktur linearer Programme, Polyedertheorie, Optimalitätskriterien, Dualität, Simplex-Algorithmus, die Ellipsoid-Methode, Schnittebenenverfahren und die Branch-and Bound Methode.

Dozent:

Assistent:

Zeit & Raum:

  • VL: Mo 10-12 Uhr in Raum GW1 A1260 (Megow)
  • UE: Di 16-18 Uhr in Raum MZH 6190 (Eberle)
  • UE: Do 08-10 Uhr in Raum MZH 1470 (Eberle)

Start: Montag, 9. April 2018

Es werden zwei Übungen angeboten. Eine davon ist speziell für Wirtschaftsinformatiker konzipiert mit verstärktem Anwendungsbezug. Weiteres dazu wird in der ersten Vorlesung am 9.4.2018 besprochen.

Literatur:

  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.
  • [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006. (studip)
DatumThema
9. AprilEinführung, Lineare Optimierungsprobleme, Graphische Repräsentation
16. AprilStandardform, Geometrie linearer Programme
23. AprilGrundversion des Simplex Algorithus
3. MaiDegenerierte Basislösungen, Kreiseln des Simplex, Tableau-Methode
7. MaiZwei-Phasen Simplex, Laufzeitverhalten
14. MaiDualität, Dualitätssätze, Komplementärer Schlupf
28. MaiMinimale Spannbäume (Prim, Kruskal), Kürzeste Wege (Dijkstra)
4. JuniFlüsse und Schnitte in Netzwerken, max-flow min-cut Theorem
11. JuniEllipsoid Methode, Separieren und Optimieren
18. JuniEinführung ganzzahliger LPs, Schnittebenenverfahren
25. JuniBranch and Bound/ and Cut Verfahren
2. Juli---entfällt---

Approximation Algorithms

Advanced Course in Summer 2018

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.

Lecturers:

Time & Room:

  • Mon 14-16 in room MZH 1090
  • Thu 10-12 Uhr in room MZH 1110

Start: Thursday, April 5, 2018

Literature: The course is based on parts of the literature below and recent research articles that will be added later.

  • [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
  • [V] Approximation Algorithms, Vijay V. Vazirani online version
DateTopic
05/04/18Introduction, greedy algorithms: k-center problem and load balancing
09/04/18Greedy algorithms: scheduling with due dates, set cover problem
12/04/18set cover (cont.), metric TSP (double tree and Christofides' Alg.), hardness of approximation for TSP (gap reduction)
19/04/18local search, load balancing, k-median
23/04/18PTASs, bin packing, load balancing
26/04/18PTAS for ETSP
07/05/18Linear programming and rounding, scheduling with release dates
14/05/18LP rounding, Prize-collecting steiner treex
17/05/18LP Duality, Exercise 3
24/05/18Exercise 3, LP-rounding, uncapacitated facility location
28/05/18Random sampling, Max SAT, Max CUT
31/05/18Randomized rounding, the best of two algorithms, Max SAT
04/06/18Scheduling by alpha-points, randomized alpha points, 1|r_j|sum (w_j)C_j
11/06/18LP Rounding, prize-collecting steiner tree, uncapacitated facility location, Chernoff bounds, multicommodity flow
14/06/18Primal-dual algorithms, set cover, shortest path, knapsack cover
18/06/18Primal-dual algorithms, uncapacitated facility location, prize-collecting steiner tree
21/06/18Exercise session
25/06/18Introduction to online optimization, ski rental, lost cow problem, doubling, list update
28/06/18Online list update, summary

Algorithmen für Big Data

Vorlesung im Sommersemester 2018

In moderner Datenverarbeitung stellt sich zunehmend häfig das Problem, dass große Mengen von Daten anfallen die nur auf günstigen aber langsamen Massenmedien gespeichert werden können. Algorithmisch stellt sich hier das Problem, dass die für eine Berechnung nötigen Daten nicht vollständig in den Hauptspeicher passen. Dieser Kurs beschäftigt sich mit Algorithmen, die trotz solcher Beschränkungen verlässliche Ergebnisse liefern.

Aufbauend auf die im Bachelorstudium erworbenen Kenntnisse soll in diesem Kurs eine solide Basis geschaffen werden, Probleme strukturiert und effizient zu lösen. Ziel des Kurses ist es, Algorithmen kennenzulernen die breite Anwendung in der Praxis finden und ein tiefes Verständnis der verwendeten Mechanismen zu erlangen. Um eine möglichst breite Anwendbarkeit der erlernten Mechanismen und Techniken zu ermöglichen wird in diesem Kurs Wert auf die mathematische Analyse der Algorithmen gelegt.

Dozent: Prof. Dr. Tobias Mömke

Theoretische Informatik 2: Berechenbarkeit und Komplexität

Vorlesung im Sommersemester 2018

Kurzbeschreibung

Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik. Sie besteht aus zahlreichen Teildisziplinen, von denen in dieser Vorlesung hauptsächlich die Theorie der Berechenbarkeit und die Komplexitätstheorie behandelt werden. In der Theorie der Berechenbarkeit geht es um die Definition abstrakter Modelle von Berechnung und um die fundamentale Frage, welche Probleme prinzipiell berechenbar sind und welche nicht. Eine zentrale Rolle spielen dabei Turingmaschinen als elementares Berechnungsmodell, das aber dennoch äquivalent zu komplexeren und praxisnäheren Modellen wie modernen Programmiersprachen ist. Die Komplexitätstheorie betrachtet zusätzlich die zur Berechnung verwendeten Ressourcen wie Laufzeit und Speicherplatz. Eine zentrale Frage ist dann, welche Probleme mit vertretbarem Aufwand berechenbar sind, wobei "vertretbarer Aufwand" meist mit "in polynomieller Zeit" gleichgesetzt wird. Zusätzlich zu den erwähnten Themen werden wir auch einige in Theoretische Informatik 1 offen gebliebene Fragen aus dem Gebiet der formalen Sprachen klären und beispielsweise ein Automatenmodell fär kontextsensitive Sprachen und Typ-0-Sprachen angeben. Im letzteren Fall sind das Turingmaschinen, was eine direkte Verbindung zwischen formalen Sprachen und der Theorie der Berechenbarkeit liefert.

Skript und Folien

... werden zu gegebener Zeit in Stud.IP zugänglich gemacht.

Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden. Hier etwas zum Thema: wie liest man einen mathematischen Text?

Organisation der Tutorien

Nähere Infos zu Terminen, Tutor_innen und Einschreibung gibt es zu gegebener Zeit auf Stud.IP.

Aufgabenblätter

An dieser Stelle In Stud.IP wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in Kleingruppen von 2–3 Personen bearbeitet und in den Tutorien gemeinsam besprochen.

Dozent: Prof. Dr. Tobias Mömke

Zeit & Raum: Montags 14:00 – 16:00 in Raum NW1 H 1 - H0020

Literatur:

  • Juraj Hromkovič, Theoretische Informatik, Springer Verlag, 2011
  • Michael Sipser, Introduction to Theory of Computation. Cengage Learning, 2013 (3rd edition)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, 2011 (3. Auflage)
  • Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
  • Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999

Advanced Algorithms (engl./dt.)

Master Seminar in Summer 2018
4 CP

In this seminar, we will read (more or less) recent papers in theoretical computer science, particularly, on efficient algorithms, online and approximation algorithms, scheduling, algorithmic game theory/mechanism design and combinatorial optimization under uncertainty. The papers may be less recent if there is interesting follow-up work. Each student gives a presentation (45 min.) followed by a discussion. These presentations will be given in one or two days at the end of the semester. The exact dates will be discussed during the organizational meeting on April 6.

Lecturer: Prof. Dr. Nicole Megow

Important: The first meeting with all organizational details and an overview of topics took place on Friday, April 6, 2018 at 09:00 in room MZH 3150.

If you are interested in this seminar then send me an email as soon as possible.

P vs NP Survival Guide

Master Seminar im Sommersemester 2018
4 ECTS

Das Seminar beschäftigt sich mit dem Thema P vs NP. Die Frage ob P = NP gilt ist äquivalent zur Frage, ob man in einem Straßennetzwerk einen Weg finden kann der alle Städte genau einmal besucht oder zur Frage, ob man in einem Netzwerk von Freunden eine Zahl k von Personen finden kann, die sich alle gegenseitig kennen.

Der fundamentale Charakter dieses bislang ungelösten Problems hat dazu geführt, dass das Clay Mathematics Institute einen Preis von USD 1 000 000 für die Lösung dieses Problems ausgeschrieben hat.

Auf dem Weg dieses Problem zu lösen gibt es jedoch viele Fallen und Sackgassen. Dies führt dazu, dass gelegentlich Nachrichten zur vermeintlichen Lösung dieses Problems in Zeitungen veröffentlicht werden. Bislang war keiner dieser Ansätze korrekt.

In diesem Seminar geht es darum, ein besseres Verständnis zu diesem Problem zu erarbeiten. Eines der Ziele ist es, zumindest einige Fallen als solche zu identifizieren um Fehler zu vermeiden. Es geht um Themen wie zum Beispiel:

  • Welche Art von Problemen kann man effizient lösen?
  • Gibt es ähnliche Klassen von Problemen bei denen eine Lösung bekannt ist?
  • Wie verifiziert man, ob ein P vs NP Beweis korrekt sein kann? Welche Lösungsansätze kann man ausschließen?
  • Ist es möglich dass die Frage ob P vs NP unentscheidbar ist?

Dozent: Prof. Dr. Tobias Mömke

Seminarvorträge:

Zeit26.07.2018
Raum MZH 5210
 
09:15NP-Schwere Beweise
Yannis Rohloff
10:15Schäfer's Dichotomy
Leif Sabellek
11:30Natural Proofs
Tobias Dellert
13:30PCP Theorem (Probabilistically Checkable Proofs)
Jens Schlöter
14:30Kolmogorov Komplexität und Verifiable Mathematics
Maurice Funk

Interessante Links

Literaturgrundlage:

  • Scott Aaronson: P=?NP. Electronic Colloquium on Computational Complexity (ECCC) 24: 4 (2017)

Shared Mobility: Modelle, Algorithmen und Optimierung

Bachelorprojekt Winter/Sommer 2017/18

für Studiengänge Informatik und Wirtschaftsinformatik

Inhalt dieses Projekts ist die Untersuchung von Anforderungen an IT-Unterstützungssysteme im Bereich der Shared Mobility. Es werden Modelle, Algorithmen und Optimierungsmethoden für Fragestellungen in Bike- und Car-Sharing Systemen entwickelt, implementiert, evaluiert und visualisiert.

Nach knapp zwei Semestern intensiver Arbeit ist das Projekt nun zu Ende. Auf dieser Webseite berichten die Studenten von ihrem Projekt.

Lecturers:

Assistent:

Projektraum: MZH 3240

Plenum: Fr 10-14 in Raum MZH 3150 (Seminarraum)

Hands-on Tutorial on Optimization (engl./dt.)

Block course in Summer 2018
3 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems.
We develop a toolkit to model real-world problems as (discrete) linear programs. Some examples of basic optimization problems that are part of this toolkit are scheduling, packing, matching, routing, and network-design. We also explore different ways to find integer solutions such as cutting planes, Branch & Bound, and column generation.
Based on this theoretical background, we focus on translating practical examples into mixed-integer linear programs. We learn how to use professional solvers (such as CPLEX, Gurobi, and FICO Xpress) and tailor the solution process to certain properties of the problem.
Throughout the course, we concentrate on modeling and solving practical problems with some theory parts in between.

Lecturers:

This course consists of two phases:

Phase 1:

  • One week of lectures and practical labs during Mon Sept 24 – Fri Sept 29 from 9:30 to 12:30 and from 13:30 to 17:30.

Phase 2:

  • One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented at the latest in the first week of the winter semester 2018/2019.

There are no prerequisites except some basic programming skills to participate.