[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.



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




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


  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

Interesting Links

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: 
LectureMo, 10-12ZIB Lecture Hall
LectureWed, 10-12ZIB Lecture Hall
Exercise SessionThu, 14-16Arnimallee 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: .

If you have any questions related to this lecture, please contact Pedro Maristany.

    Office hours   Office   Phone   E-mail
Prof. Dr. Ralf Borndörfer   by appointment   ZIB 3033   84185 - 243
Pedro Maristany   by appointment   ZIB 3003   84185 - 232