News:

[03.05.2018] The (almost final version of the) third exercise sheet was uploaded.

[26.04.2018] New section "Interesting Links". So far it only contains a link to the interactive Goldberg-Tarjan algorithm.

[26.04.2018] Next week both lectures will be on Wednesday (starting at 08:30) in the lecture hall 2005. There will be no lecture on Monday.

[26.04.2018] The second exercise sheet was uploaded.

A new version of the 1st exercise sheet was uploaded. In Exercise 1, the fee function f has to be monotonically increasing.

Content:

News

16.04.18 There will be a seminar on Shortest Path Problems and a lecture on Public Transportation Networks next semester

Seminar: http://www.zib.de/node/3446

Lecture: http://www.zib.de/node/3447

This lecture is the third part of the optimization lecture series. The contents list will be updated soon.

Content

1. Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
2. Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen
3. Das Rucksackproblem
4. Branch-and-Bound-Verfahren
5. Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
6. Polyedrische Kombinatorik: Theorie, Beispiel

Proof of Hoffman's Circulation Theorem (Exercise Sheet 1, Exercise 4)

Interactive Goldberg-Tarjan (Preflow-Push) algorithm

Target audience

Students of Mathematics with background knowledge in Linear Algebra, Calculus, and Linear and Non-Linear Opimization. To solve some of the exercises the usage of a computer will be required.

M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte

V. Chvátal, Linear Programming, Freeman 1983

G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963

R. Rockafellar, Convex Analysis, Princeton University Press, 1970

Nemhauser, George L., and Laurence A. Wolsey. Integer programming and combinatorial optimization, 1988.

B. Korte, J. Vygen. Combinatorial Optimization, 2000. (German Edition: Kombinatorische Optimierung)

Interactive Graph Algorithms (in German)

Schedule & Location:
 Lecture Mo, 10-12 ZIB Lecture Hall Lecture Wed, 10-12 ZIB Lecture Hall Exercise Session Thu, 14-16 Arnimallee 6, 025/026

Requirements & Formalities:

This lecture is listed in the official lectures' schedule of the Freie Universität Berlin for the summer semester 2018: http://www.fu-berlin.de/vv/de/lv/447698?query=Bornd%C3%B6rfer&sm=38382 .