<h4><strong>News</strong></h4><p>16.02.18 The second exam will take place on Thursday the <strong>12th of April, 10:00-12:00</strong>, in the <strong>ZiB Seminar Room</strong> (besides the lecture hall).</p><p>20.02.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>Diese Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil II behandelt die Ganzzahlige Optimierung.</p><p><strong>Inhalt</strong></p><ol><li>Grundlagen der Nichtlinearen Optimierung: Quadratische Optimierungsprobleme, Behandlung von Gleichungen, Behandlung von Ungleichungen mit der Active Set Methode</li><li>Innere-Punkte-Verfahren: Karmarkar-Algorithmus, Barriere-Methoden, zentraler Pfad</li><li>Ellipsoidmethode: Löwner-John-Ellipsoid, Lineare Optimierung</li><li>Grundlagen: Problemformulierungen, Beispiele und Anwendungen, Kombinatorische Optimierungsprobleme, Graphentheorie, Datenstrukturen zur Speicherung von Graphen</li><li>Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit</li><li>Bäume und Branchings: Bäume, Wälder, Branchings, Arboreszenzen</li><li>Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Orakel, Optimierung über Unabhängigkeitssystemen</li><li>Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs</li><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>&nbsp;</p><p>&nbsp;<strong>Zielgruppe</strong></p><p>Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Linearer Algebra, Analysis, Linearer und nicht-linearer Optmierung. Einige Übungsaufgaben erfordern den Einsatz eines Computers.<br /><br /></p><div class="row"><div class="col-md-12"><div class="form-group"><strong> <label for="references">Literatur</label></strong><div><div><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></div></div></div></div></div> <table border="1" frame="void" rules="rows"><tbody><tr><td>&nbsp;Vorlesung</td><td>&nbsp;Mo, 10-12</td><td>&nbsp; Takustr. 7, ZIB Hörsaal</td></tr><tr><td>&nbsp;Vorlesung</td><td>&nbsp;Mi, 10-12</td><td>&nbsp; Takustr. 7, ZIB Hörsaal</td></tr><tr><td>&nbsp;Übung</td><td>&nbsp;Tu, 14-16</td><td>&nbsp; Arnimallee 6, SR 031</td></tr></tbody></table> <p>Bei Fragen zu dieser Veranstaltung kontaktieren Sie bitte Isabel Beckenbach (siehe unten).</p> <table border="0" rules="rows"><tbody><tr><td>&nbsp;</td><td>&nbsp; Sprechstunde</td><td>&nbsp; Raum</td><td>&nbsp; Telefon</td><td>&nbsp; E-mail</td></tr><tr><td><a href="http://www.zib.de/borndoerfer/">Prof. Dr. Ralf Borndörfer</a></td><td>&nbsp; auf Anfrage</td><td>&nbsp; <a href="http://www.zib.de/contact">ZIB</a> 3033</td><td>&nbsp; 84185 - 243</td><td><p>&nbsp; borndoerfer@zib.de</p></td></tr><tr><td>&nbsp;<a href="http://www.zib.de/members/beckenbach">Isabel Beckenbach</a></td><td>&nbsp; auf Anfrage</td><td>&nbsp; <a href="http://www.zib.de/contact">ZIB</a> 3301</td><td>&nbsp; 84185 - 134</td><td><p>&nbsp; beckenbach@zib.de</p></td></tr></tbody></table> ex1.pdf ex2-tex.pdf ex3.pdf ex4.pdf ex5.pdf ex6.pdf ex7.pdf ex8.pdf ex9.pdf ex10.pdf ex11.pdf ex12.pdf ex13.pdf result1.pdf WS1718-OptII-Klausur-Ergebnisse.pdf