Geometrie und Optimierung
Sommersemester 2010
Ankündigungen
Am Mittwoch, den 8. September, 14:00-14:30 besteht die Möglichkeit, die Nachklausur einzusehen.

Die Nachklausur wurde am Montag, den 23.8., 10-12 in Raum SR 31 der Arnimallee 6 geschrieben.
Wenn Sie mitgeschrieben haben und der Veröffentlichung Ihrer Note auf dieser Seite zugestimmt haben, können Sie Ihr Ergebnis mit diesem Link abfragen (die Ergebnisse der Hauptklausur finden sie hier.). (Sowohl Benutzername als auch Passwort sind Ihre Matrikelnummer). Wenn Sie dem Aushang an meiner Bürotür zugestimmt haben, können Sie dort nachsehen (A3, 202).



Die Klausur wurde am Mittwoch, den 14.7.2010 von 10-12 im SR31 in der Arnimallee 6 geschrieben.
Ich wünsche Ihnen eine schöne verbleibende vorlesungsfreie Zeit.
Themen
Im Zentrum der Vorlesung werden Polyeder und ihre Bedeutung in linearer und ganzzahliger Optimierung stehen. In ersten Teil der Vorlesung werden uns ausführlich mit der geometrischen und kombinatorischen Struktur von Polyedern beschäftigen. Insbesondere werden wir den Dualätssatz der Polyedertheorie beweisen, der uns sagt, daß wir Polyeder einerseits als Schnitt von Halbräumen und andererseits als Summe der konvexen und positiven Hülle von Punkten schreiben können. Mit seiner Hilfe wollen wir versuchen, die geometrische und kombinatorische Struktur von Polyedern zu verstehen.
In der linearen Optimierung geht es darum, ein lineares Funktional über einem Polyeder zu maximieren. Viele Optimierungsprobleme in Anwendungen sind von diesem Typ, oder lassen sich leicht darauf zurückführen. Wir werden insbesondere den Simplexalgorithmus und einige Varianten zum Lösen dieser Aufgabe kennenlernen. Der Dualitätssatz ergibt ein duales Optimierungsproblem, mit dessen Hilfe man effizientere Algorithmen angeben und die Struktur linearer Optimierungsprobleme besser verstehen kann.
Anwenden werden wir diese Theorie unter anderem auf Probleme aus der Graphentheorie. Insbesondere werden wir einige der Min-Max-Sätze aus der Graphentheorie auf geometrische Art wiederentdecken (z.B. MaxFlow-MinCut, oder Mengers Satz).
Anschießend betrachten wir ganzzahlige lineare Optimierung. Hier wollen wir wieder ein lineares Funktional über einem Polyeder maximieren, aber wir fordern zusätzlich, daß die Lösung ganzzahlig sein soll. Das ist eine in Anwendungen sehr oft vorkommende Annahme. Wir werden Lösungsansätze für ganzzahlige lineare Programme kennenlernen und untersuchen, warum solche schwieriger sind als lineare Programme.
Dabei werden wir unter anderem auch ganzzahlige Polyeder untersuchen, also Polyeder, in denen alle Ecken ganzzahlige Koordinaten haben.
Zeiten
  • Vorlesung (Andreas Paffenholz):
    • Mo, Mi 10 - 12, SR 32, A6

  • Tutorien
    • Do 12 - 14, SR 31, A6 (Laszlo David)
    • Mi 12-14, SR 119, A3 (Kaie Kubjas)
Sprechstunden
während des Semesters: Di 14 - 15, sont nach Vereinbarung
(Zimmer 202, Arnimallee 3).

Laszlo David
n.V.
().

Kaie Kubjas
n.V.
(Zimmer 202, Arnimallee 3).

Software
Wenn Sie mit Polyedern und Linearen Programmen experimentieren wollen, gibt es eine ganze Reihe sehr guter Softwarepakete, die Sie dafuer benutzen können. Alle Programme laufen unter Linux, Unix, und Mac OS, die Visualisierungsprogramme und SoPlex auch unter Windows.
  • Die beiden Programme cdd und lrs können zwischen Ecken- und Facettendarstellung umrechnen.
  • Mit JavaView oder geomview können Sie zwei- und dreidimensionale Polyeder visualisieren.
  • polymake kann, zum Teil mit Hilfe anderer Programme, sehr viele Berechnungen mit Polytopen und Graphen ausführen, insbesondere konvexe Hüllen ausrechnen, Seiten bestimmen, Polytope visualisieren, und einfache lineare Programme lösen.
  • Zum Lösen komplizierterer linearer Programme können Sie z.B. eines der Programme SoPlex oder lp_solve verwenden.
Von den genannten Programmen ist leider nur JavaView auf den Rechnern am Fachbereich installiert.
Vorlesungsnotizen
Datum Inhalt
Skript vom
12.04. Polyeder und Lineare Programme
Affine Unterräume, konvexe Mengen und Kegel
[pdf] 18.05.10
14.04. Fourier-Motzkin-Elimination
19.04. polyedrische und endlich erzeugte Kegel
Farkas-Lemma
26.04. Minkowski-Weyl-Dualität
Charakteristischer Kegel
Linealitätsraum
spitze Polyeder.
[pdf] 18.05.10
28.04. Lineare Programmierung
Notation, Beispiele
Standardform, kanonische Form
Wechsel zwischen Darstellungen
Schwacher Dualitätssatz
[pdf] 18.05.10
03.05. Dualitätssatz
Regeln für das Aufstellen dualer Programme
Satz vom komplementären Schlupf
05.05. Beestimmen der dualen Lösung
geometrische Interpretation
10.05. Seiten von Polyedern
Definitionen, Beispiele
Darstellung durch lineare Funktionale
[pdf] 07.06.10
12.05. Darstellung von Seiten als Schnitt von Ungleichungen
redundante Ungleichungen
Facetten
17.05. Facetten und irredundante Ungleichungen
minimale Seiten
19.05. innere Darstellung von beschränkten Polyedern
26.05. innere Darstellung von Kegeln
31.05. Innere Darstellung von Polyedern
Eindeutigkeit
spitze Polyheder
02.06. Simplex-Algorithmus
Basislösungen, Basis
Degenerierte/nichtdegenerierte Lösungen
Beispiele
[pdf] 21.06.10
07.06. Simplex-Tableau
reduzierte Kosten
Phase II des Algorithmus
09.06. Bestimmung einer Anfangslösung
Phase I des Algorithmus
Zykeln
14.06. Zykeln
Spalten/Zeilenauswahl
lexikographische Zeilenauswahl
revised Simplex
16.06. reduzierte Tableaus
dualer Simplex-Algorithmus
[pdf] 05.07.10
21.06. Updates in reduzierten Tableaus, primale/duale Schritte
Bestimmung einer Anfangslösung mit dualem Algorithmus
23.06. Rationale und ganzzahlige Polyeder
Definitionen
Charakterisierung
[pdf] 05.07.10
28.06. Gitter und unimodulare Abbildungen
uimodulare/total unimodulare Matrizen
ganzzahlige Polyeder bei
unimodularen Gleichungssystemen.
[pdf] 10.07.10
30.06. ganzzahlige Polyeder bei
unimodularen Gleichungssystemen.
Beispiele unimodularer Matrizen
Inzidenzmatrizen von Graphen
05.07. Matchingpolytope [pdf] 10.07.10
07.07. Matching- und Knotenüberdeckungszahl
Kantenüberdeckungszahl und stabile Mengen
gewichtete Versionen
[pdf] 10.07.10
12.07. Flüsse in Graphen
Schnitte
MaxFlow-MinCut-Satz
14.07. Klausur
Übungsaufgaben
Die Übungsaufgaben sollen in einzeln oder in Zweiergruppen bearbeitet und abgegeben werden. Sie müssen bis spätestens am auf die Ausgabe folgenden Montag vor der Vorlesung abgegeben werden (Ausnahme: ersten Blatt bis Mittwoch vor der Vorlesung).
Datum Thema
Abzugeben bis
14.4. Affine Unterräume, konvexe Mengen und Kegel 21.4.
19.4. Kegeldualität und Farkas-Lemma (korrigiert) 26.4.
26.04. H- und V-Beschreibung von Polyedern, Minkowskisummen 03.05.
03.05. Lineare Programmierung und Dualität 10.05.
10.05. Seiten von Polyedern (1. Aufgabe korrigiert!) 17.05.
17.05. Seiten von Polyedern 26.05.
24.05. Polytope 31.05.
31.05. Kegeldualität 07.06.
07.06. Simplex-Algorithmus 14.06.
14.06. Simplex-Algorithmus 21.06.
21.06. Änderung in den Daten 28.06.
28.06. ganzzahlige Polyeder 05.07.
05.07. Zusatzblatt, ganzzahlige Polyeder 12.07.
Literatur
Ab Semesteranfang werden einige Bücher im Handapparat in der Bibliothek für diese Vorlesung reserviert sein.
  • Barvinok, A Course in Convexity, AMS
  • Chvatal, Linear Programming, Freeman
  • Korte, Vygen, Combinatorial Optimization, Springer
  • Matousek, Gärtner, Understanding and Using Linear Progamming, Springer
  • Shrijver, Combinatorial Optimization -- Polyhedra and Efficiency, Springer
  • Shrijver, Linear and Integer Programming, Wiley
  • Ziegler, Lectures on Polytopes, Springer
Voraussetzungen
Gute Kenntnisse in linearer Algebra (Teil I). Kenntnisse in Graphentheorie sind hilfreich, aber nicht unbedingt notwendig.
Scheinkriterien
Um die 10 ECTS-Punkte zu bekommen ist es notwendig:
  • regelmäßig am Tutorium teilzunehmen (d.h. höchstens zweimal zu fehlen)
  • zu mindestens der Hälfte der Übungsaufgaben korrekte Lösungen einzureichen und
  • die Klausur am Ende des Semesters zu bestehen.
  • Ihre Note bestimmt sich ausschließlich aus Ihrem Abschneiden in der Klausur.