<p>[03.05.2018] The (almost final version of the) third exercise sheet was uploaded.</p><p>[26.04.2018] New section "Interesting Links". So far it only contains a link to the interactive Goldberg-Tarjan algorithm.</p><p>[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.</p><p>[26.04.2018] The second exercise sheet was uploaded.</p><p>A new version of the 1st exercise sheet was uploaded. In Exercise 1, the fee function f has to be monotonically increasing.</p> <p>&nbsp;<strong>News</strong></p><p>16.04.18 There will be a <strong>seminar</strong> on Shortest Path Problems and a <strong>lecture</strong> on Public Transportation Networks <strong>next semester</strong></p><blockquote><p>Seminar: <a href="http://www.zib.de/node/3446">http://www.zib.de/node/3446</a></p><p>Lecture: <a href="http://www.zib.de/node/3447">http://www.zib.de/node/3447 </a></p></blockquote><p>&nbsp;</p><p>This lecture is the third part of the optimization lecture series. The contents list will be updated soon.</p><p><strong>Content</strong></p><ol><li>Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme</li><li>Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen</li><li>Das Rucksackproblem</li><li>Branch-and-Bound-Verfahren</li><li>Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung</li><li>Polyedrische Kombinatorik: Theorie, Beispiel</li></ol><p><strong>Interesting Links</strong></p><p><a href="http://www.sfu.ca/~mdevos/notes/misc/hof-circ.pdf">Proof of Hoffman's Circulation Theorem (Exercise Sheet 1, Exercise 4)</a></p><p><a href="http://www.adrian-haarbach.de/idp-graph-algorithms/implementation/maxflow-push-relabel/index_en.html">Interactive Goldberg-Tarjan (Preflow-Push) algorithm</a></p><p>&nbsp;</p><p>&nbsp;<strong>Target audience<br /></strong></p><p>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.<br /><br /></p><p><strong>&nbsp; <label for="references">Literature</label></strong></p><p>M. Grötschel, Lineare Optimierung, <a href="http://www.zib.de/groetschel/teaching/materials.html">eines der Vorlesungsskripte</a></p><p>V. Chvátal, Linear Programming, Freeman 1983</p><p>G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963</p><p>R. Rockafellar, Convex Analysis, Princeton University Press, 1970</p><p>Nemhauser, George L., and Laurence A. Wolsey. Integer programming and combinatorial optimization, 1988.</p><p>B. Korte, J. Vygen. Combinatorial Optimization, 2000. (German Edition: Kombinatorische Optimierung)</p><p><a title="Interactive Graph Algorithms" href="http://www-m9.ma.tum.de/Allgemeines/GraphAlgorithmen">Interactive Graph Algorithms (in German)</a></p> <table style="width: 398px; height: 14px;" border="1" frame="void" rules="rows"><tbody><tr><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td></tr></tbody></table><table border="0" cellspacing="2" cellpadding="2" align="left"><tbody><tr><td>Lecture</td><td>Mo, 10-12</td><td>ZIB Lecture Hall</td></tr><tr><td>Lecture</td><td>Wed, 10-12</td><td>ZIB Lecture Hall</td></tr><tr><td>Exercise Session</td><td>Thu, 14-16</td><td>Arnimallee 6, 025/026</td></tr></tbody></table><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p> <p>This lecture is listed in the official lectures' schedule of the Freie Universität Berlin for the summer semester 2018: <a href="http://www.fu-berlin.de/vv/de/lv/447698?query=Bornd%C3%B6rfer&amp;sm=383825" target="_blank">http://www.fu-berlin.de/vv/de/lv/447698?query=Bornd%C3%B6rfer&amp;sm=38382</a> .</p><p>If you have any questions related to this lecture, please contact Pedro Maristany.</p> <table border="0" align="left"><tbody><tr><td>&nbsp;</td><td>&nbsp;&nbsp; Office hours</td><td>&nbsp;&nbsp; Office</td><td>&nbsp;&nbsp; Phone</td><td>&nbsp;&nbsp; E-mail</td></tr><tr><td>Prof. Dr. Ralf Borndörfer</td><td>&nbsp;&nbsp; by appointment</td><td>&nbsp;&nbsp; ZIB 3033</td><td>&nbsp;&nbsp; 84185 - 243</td><td>&nbsp;&nbsp; borndoerfer@zib.de</td></tr><tr><td>Pedro Maristany</td><td>&nbsp;&nbsp; by appointment</td><td>&nbsp;&nbsp; ZIB 3003</td><td>&nbsp;&nbsp; 84185 - 232</td><td>&nbsp;&nbsp; maristany@zib.de</td></tr></tbody></table><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p><p>&nbsp;</p> ex1.pdf ex2.pdf ex3.pdf