Content: 

News

23.10.17 The exercise class is shifted to Tuesday 14:15-15:45 in SR 013, Arnimallee 6. Next exercise is on 24.10.17.

02.11.17 The second exercise sheet is online.

07.11.17 The third exercise sheet is online.

14.11.17 The fourth exercise sheet is online.

 

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

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