Research Group Lattice Polytopes

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.

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.

• 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)

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.

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

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.

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

Gute Kenntnisse in linearer Algebra (Teil I). Kenntnisse in Graphentheorie sind hilfreich, aber nicht unbedingt notwendig.

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.