Summer 2019

Algorithmische Diskrete Mathematik

Sommersemester 2019
03-M-WP-18, 6 CP (+3 CP bei optionaler Zusatzleistung)

Inhalt

  • Einführung in Graphentheorie, kombinatorische und lineare Optimierung
  • Graphentheorie: Grundbegriffe, Wege in Graphen, Euler- und Hamiltonkreise, Bäume
  • Algorithmische Grundlagen (Kodierungslänge, Laufzeit, Polynomialzeitalgorithmen)
  • Spannbäume, Matchings, Netzwerkflüsse und -schnitte (kombinatorische Algorithmen)
  • Einblick in lineare Optimierung: Modellierung und Struktur linearer Programme, Polyeder, Optimalitätskriterien, Dualität, Simplex-Algorithmus
  • Elemente der Komplexitätstheorie

Lecturer:

Assistent:

Time & Room:

  • Do 10-12 Uhr in Raum MZH 6210 (Vorlesung)
  • Mi 10-12 Uhr in Raum MZH 6340 (Übung)

Start:

  • Donnerstag, 4. April 2019
DatumThema
4. AprilEinführung
11. AprilBäume, Minimale aufspannende Bäume (Prim, Kruskal), Clustering
25. AprilGrundlagen Algorithmen, Korrektheit und Laufzeit, Breitensuche
2. MaiKürzeste Wege, Dijkstra's Algorithmus
9. MaiKürzeste Wege II (Bellman-Ford, Floyd-Warshall), Dynamische Programmierung, Knapsack Problem
16. MaiNetzwerkflüsse, Max Fluss/Min Schnitt Theorem
23. MaiMatchings, Satz von König, Satz von Hall
29. MaiHungarische Methode - Selbststudium
13. JuniMatchings, Satz von Berge, stabile Matchings
20. JuniEinblick in Komplexitätstheorie (P, NP, polynomielle Reduktion, NP-schwer/vollständig, Beispiele)
27. JuniApproximationsalgorithmen, Metrisches TSP, Christofides, Inapproximierbarkeit
4. JuliEinblick in Lineare Optimierung
11. JuliEinblick in Online Optimierung, Zusammenfassung/Überblick

Geben Sie bitte bei Abgabe der Übungsblätter die Namen und Matrikelnummern aller Mitwirkenden ab.

Literatur:

  • [KV] Korte, Vygen: Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2012.
  • [KN] Krumke, Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer-Vieweg, 2012.
  • [CLRS] Corman, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd edition, MIT Press, 2009.
  • [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006.
  • [AMO] Ahuja, Magnanti, Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.


ADM Zusatzseminar - 17.9.19, MZH 1110

08:30 - 09:15   Angelina Matis: Minimum Bounded Degree Spanning Trees (deutsch)
09:25 - 10:10   Gideon Klaila: Expander graphs and their applications
10:30 - 11:15   Nele Schriefer: Approximation Algorithms for distance-constrained vehicle routing
11:25 - 12:10   Arndt Kathmann: Introduction to algorithmic game theory: Routing games

13:15 - 14:00   Oliver Link: Maintaining Matchings Online (deutsch)

Approximation Algorithms

Master Course in Summer 2019
03-ME-602.99a, 6 CP

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 rigorous bounds on their worst case performances.

Lecturers:

Time & Room:

  • Tue 12-14 in room MZH 6210
  • Thu 12-14 in room MZH 6210

Start:

  • Tuesday, April 2, 2019

Examination:

  • The examination will be by individual oral exam. A 1/3 mark bonus is awarded to students who correctly solve 60% of the homework exercises.

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
  • [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiří Matoušek, Springer, 2012.
DateTopic
02/04/19Introduction, greedy algorithms: k-center problem and load balancing
04/04/19Greedy algorithm for Set Cover, refresher on NP-completeness.
09/04/19Exercise session 1: hardness of approximation for k-center, analysis of greedy algorithms.
11/04/19TSP and Christofides' algorithm.
23/04/19Local search: identical parallel machines and k-median.
25/04/19Exercise session 2: polynomial run time for k-median, local search for uncapacitated facility location.
30/04/19A quick refresh/intro to linear programming; deterministic rounding for approximation algorithms.
02/05/19Refresh/intro to LP duality; minimizing sum of completion times.
07/05/19Exercise session 3: LPs, separation oracles.
09/05/19Weighted sum of completion times, approximating SAT with fair coin flipping.
14/05/19Max SAT via biased coins and via randomized non-linear LP rounding.
16/05/19Exercise session 4: Card tricks and directed cut.
21/05/19LP modeling.
23/05/19Rounding the Price collecting steiner tree LP.
28/05/19Exercise session 5: Integrality gaps.
30/05/19 -- 07/06/19No lectures
11/06/19Knapsack cover integrality gap and online optimization.
13/06/19PTAS for the Knapsack and P||Cmax problems.
18/06/19PTAS for Euclidean TSP.
20/06/19Semidefinite programming and rounding for Max Cut.
24/06/19Coloring 3-colorable graphs with SDPs.
27/06/19Finishing vector colorings, how to use Wigderson's trick.
02/07/19The Primal-dual method.
04/07/19The Primal-dual method 2.
09/07/19Exercise session 6: Primal-dual algorithms.

 

 

Operations Research

Sommersemester 2019, 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.

Dozent:

Assistent:

Zeit & Raum:

  • Vorlesung: Di 10-12 Uhr in Raum MZH 6210 (Megow)
  • Übung: Do 12-14 Uhr in Raum MZH 6340 (Eberle)
  • Betreute Rechnerübung: Do 14-16 Uhr in Raum MZH 3510 (Eberle) ab Ende April

Start:

  • Dienstag, 2. April 2019

In der Übung donnerstags von 12-14 Uhr werden die Übungsblätter besprochen. Der Termin von 14-16 Uhr ist die betreute Rechnerübung, in der die Studenten die Möglichkeit haben, die Programmieraufgaben zu lösen und gezielte Fragen zu stellen.
Die Übung am 27. Juni findet von 14:15 bis 15:45 in Raum MZH 3150 statt.

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.
DatumThema
2. AprilEinführung, Lineare Optimierungsprobleme, Graphische Repräsentation
9. AprilStandardnormalform, Konvexität und Geometrie linearer Programme
16. April-- Osterferien --
23. AprilSimplex Algorithmus, Tableau Methode, Pivotregeln (Kreiselvermeidung)
30. AprilZweiphasen-Simplex, Dualität
7. MaiInterpretation und Anwendungen zur Dualität, Einführung Begriffe zur Graphentheorie
14. MaiGanzzahlige Lineare Programme, Primal-duale Algorithmen, totale Unimodularität, Netzwerkdesign (Min. Spannbaum)
21. MaiKürzeste Wege
28. MaiDynamische Programmierung: Kürzeste Wege und Rucksackproblem
4. Juni-- keine VL --
11. JuniNetzwerkflüsse, Ford-Fulkerson Alg, Max-Fluss Min-Schnitt Theorem
18. JuniKardinalitätsmaximale Matchings in bipartiten Graphen, stabile Matchings
25. JuniBranch & Bound Verfahren, Beispiele: ILP, Knapsack, TSP
2. JuliSchnittebenen, Gomory-Chvatal, Schnittebenen-Verfahren
9. JuliAusblick, Zusammenfassung, Prüfungsvorbereitung

Diskrete Strukturen: Kombinatorik, Graphen, Färbungen

Proseminar im Sommersemester 2019
03-BE-699.13, 4 CP (+1 CP bei Zusatzleistung)

Das Seminar behandelt grundlegende Fragestellungen, Techniken und Resultate zu diskreten Strukturen. Zu den Themen gehören Kombinatorik, Induktion, Graphen, Bäume, Färbungen und Matchings. Beispiele für Fragestellungen sind:

  • Wie färbt man eine Landkarte mit wenigen Farben so dass benachbarte Länder verschiedene Farben haben?
  • Wie erhält man eine maximale Anzahl von Paaren (z.B. Zuordnungen von Arbeitnehmern und Arbeitgebern)?
  • Welche grundlegenden Möglichkeiten gibt es, kombinatorische Beweise zu führen?
  • Wie sortiert man eine Menge von Zahlen?
  • Wie zählt man Bäume?

Die Seminarvorträge werden in einer 1-2 tägigen Blockveranstaltung am Ende des Semesters bzw. am Beginn der Semesterferien gehalten. Details, Termine und Themen werden in der Vorbesprechung abgestimmt.

Dozent:


Termin:

  • Mittwoch, 3. April 2019, 14:00-15:00 im MZH 3150 (einmalig), Vorbesprechung und Themenvergabe


Literaturgrundlage:

  • Lovász, Pelikan, Vesztergombi: Diskrete Mathematik, Springer 2005
  • Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg-Teubner, 4. Auflage, 2011
  • Steger: Diskrete Strukturen 1, Springer, 2002

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

Block course in Summer 2019 (Sep 23–27)
03-BE-699.12, 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:

  • One week of lectures and practical labs during Mon Sept 23 – Fri Sept 27 from 9:00 to 12:30 and from 13:30 to 17:00 in room MZH 6210.
  • 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 2019/2020.

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

DayTopic
1Introduction, Modeling, Using GAMS
2Matrix and Polyhedral Representations,
Integer Linear Programming Tools,
Cutting Planes and Symmetry
3Branch&Bound, TSP, CPLEX guest lecture
4LP Duality, Modeling Tricks
5Column Generation, Non-Optimal Solutions, Using Other Environments
 Final Assignment

 

DayExercises
1Chips Factory,
Crude Oil Processing
2Graph Coloring,
Farm Planning
3Cheese Coup
4Cheese Empire
5Maintenance Scheduling
 Final Assignment