SoSe18: Optimization III
[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.
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
- Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
- Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen
- Das Rucksackproblem
- Branch-and-Bound-Verfahren
- Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
- 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)
| Lecture | Mo, 10-12 | ZIB Lecture Hall |
| Lecture | Wed, 10-12 | ZIB Lecture Hall |
| Exercise Session | Thu, 14-16 | Arnimallee 6, 025/026 |
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 .
If you have any questions related to this lecture, please contact Pedro Maristany.
| Office hours | Office | Phone | ||
| Prof. Dr. Ralf Borndörfer | by appointment | ZIB 3033 | 84185 - 243 | borndoerfer zib.de |
| Pedro Maristany | by appointment | ZIB 3003 | 84185 - 232 | maristanyzib.de |
