Content: 

News

16.02.18 The second exam will take place on Thursday the 12th of April, 10:00-12:00, in the ZiB Seminar Room (besides the lecture hall).

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

 

Diese Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil II behandelt die Ganzzahlige Optimierung.

Inhalt

  1. Grundlagen der Nichtlinearen Optimierung: Quadratische Optimierungsprobleme, Behandlung von Gleichungen, Behandlung von Ungleichungen mit der Active Set Methode
  2. Innere-Punkte-Verfahren: Karmarkar-Algorithmus, Barriere-Methoden, zentraler Pfad
  3. Ellipsoidmethode: Löwner-John-Ellipsoid, Lineare Optimierung
  4. Grundlagen: Problemformulierungen, Beispiele und Anwendungen, Kombinatorische Optimierungsprobleme, Graphentheorie, Datenstrukturen zur Speicherung von Graphen
  5. Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit
  6. Bäume und Branchings: Bäume, Wälder, Branchings, Arboreszenzen
  7. Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Orakel, Optimierung über Unabhängigkeitssystemen
  8. Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs
  9. Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
  10. Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen
  11. Das Rucksackproblem
  12. Branch-and-Bound-Verfahren
  13. Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
  14. Polyedrische Kombinatorik: Theorie, Beispiel

 

 Zielgruppe

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.

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: 
 Vorlesung Mo, 10-12  Takustr. 7, ZIB Hörsaal
 Vorlesung Mi, 10-12  Takustr. 7, ZIB Hörsaal
 Übung Tu, 14-16  Arnimallee 6, SR 031
Requirements & Formalities: 

Bei Fragen zu dieser Veranstaltung kontaktieren Sie bitte Isabel Beckenbach (siehe unten).

Contact: 
   Sprechstunde  Raum  Telefon  E-mail
Prof. Dr. Ralf Borndörfer  auf Anfrage  ZIB 3033  84185 - 243

  borndoerferzib.de

 Isabel Beckenbach  auf Anfrage  ZIB 3301  84185 - 134

  beckenbachzib.de