Einführung in die Lineare und Kombinatorische Optimierung (ADM I)

Beschreibung: Zur Seite des Instituts für
                Mathematik

 

Wintersemester 2014/2015

 

LV-Nr.: 3236 L 148

 

Prof. Dr. Dr. h.c. mult. Martin Grötschel   und   Dr. Axel Werner


MitteilungenBeschreibung: (down)  Downloads Beschreibung: (down) Inhalt Beschreibung: (down) Anmeldung   Ort und Termine Voraussetzungen Beschreibung: (down)  Kontakt Beschreibung: (down)  Literatur Beschreibung: (down)  Zusatzinformationen Beschreibung: (down)


Mitteilungen

Im Wintersemester 2014/2015 halte ich gemeinsam mit Dr. Axel Werner die Vorlesung "Einführung in die Lineare und Kombinatorische Optimierung (ADM I)". Diese Vorlesung ist der erste Teil der Vorlesungsserie "Algorithmische Diskrete Mathematik (ADM)", die am Institut für Mathematik der TU Berlin gehalten wird.
In der Veranstaltung werden algorithmische und strukturelle Grundlagen der Linearen und Kombinatorischen Optimierung vermittelt. Dazu gehören Grundlagen der Graphen- und Polyedertheorie und das Erlernen algorithmischer Denk- und Arbeitsweisen wie Komplexität von Problemklassen, Effizienz von Algorithmen und Approximation am Beispiel von ausgewählten praxisnahen Optimierungsaufgaben.

Die Modulbeschreibung zur Vorlesung "Einführung in die Lineare und Kombinatorische Optimierung (ADM I)" finden Sie hier.

Information zur Abschlussprüfung (und Nachklausur)
Die Abschlussprüfung in Form einer schriftlichen Klausur findet am 12. Februar 2015 (ab 16:15 Uhr im Hörsaal MA 043) statt.
Zusätzlich wird eine Nachklausur am 10. April um 10 Uhr angeboten (Raum wird noch bekannt gegeben).


Die Klausureinsicht findet am Montag, dem 23.02.2015 von 10 bis 12 Uhr in Raum MA315 statt.

Die Nachklausur findet am 10. April 2015 (ab 10:15 Uhr im Hörsaal MA 041) statt.
Die Anmeldung zur Klausur ist online über QISPOS möglich.


Downloads

Hier finden Sie das Vorlesungsskript ADM I in der endgültigen Version vom 16.02.2015.

Übungsblätter/Seminare:


Folien/Vorlesungen:

Inhalt

Kurze Einführung in die Theorie der Graphen, Digraphen und Netzwerke. Überblick über Themen und mathematische Teilgebiete der Optimierung sowie Modellierung von Fragestellungen der Praxis. Einführung in die Lineare Optimierung: Struktur und Geometrie linearer Programme, Dualitätstheorie, Transformation auf Standardformen, Basen, primale und duale Zulässigkeit. Ausführliche Darstellung des Simplex-Verfahrens in seiner Grundversion, geometrische Interpretation. Polynomiale Algorithmen für Basisprobleme der kombinatorischen Optimierung werden an Beispielen erläutert: aufspannende Bäume, kürzeste Wege, maximale Flüsse, Flüsse mit minimalen Kosten usw. In der Vorlesung werden auch die Grundlagen der Komplexitätstheorie vorgestellt: Die Klassen P und NP, NP-Vollständigkeit. Es werden Beispiele für NP-schwere Probleme gegeben (Cliquen-, Travelling Salesman-, Maximalschnitt- und Färbungsprobleme).

Anmeldung

Bitte melden Sie sich, wenn Sie die Vorlesung besuchen wollen, elektronisch an (Name, Vorname, Matrikelnummer, Studienfach (Master oder BSc bitte auch angeben), Semesterzahl, E-Mailadresse). Klicken Sie bitte auf Anmeldung.

Ort und Termine Beschreibung: (down)

Im Wintersemester 2014/2015 (15.10.14 - 14.02.2015) finden wöchentlich zwei Vorlesungen zu je 90 Minuten statt.

Vorlesungsort: TU Berlin, Mathematikgebäude, Raum: MA 041 oder MA 043 (in Abhängigkeit vom Termin).

Mittwochs,    10:00 - 12:00 Uhr, MA 041
Donnerstags, 16:00 - 18:00 Uhr, MA 043

Die erste Vorlesung findet statt am:
Mittwoch, 15. Oktober 2014, TU Berlin, Mathematikgebäude, Hörsaal MA 041, Beginn: 10:15 Uhr.

Die Übungen finden jeweils freitags in der TU statt (14:00 - 16:00 Uhr, MA 041), verantwortlich: Torsten Klug (Zuse-Institut Berlin, E-Mail: klug@zib.de).

Die erste Übung findet statt am:
Freitag, 17.10.2014, 14:00 - 16:00 Uhr, in der TU Berlin, Mathematikgebäude, in MA 041.

Tutorien (Tutor: Benedikt Bodendorf, TU Berlin, E-Mail: bodendor@math.tu-berlin.de) finden zu folgenden Terminen statt:
Di. 14:00 - 16:00 Uhr, Raum MA 751
Mi. 12:00 - 14:00 Uhr, Raum MA 313
Mi. 14:00 - 16:00 Uhr, Raum E-N 185



Voraussetzungen

Wünschenswert sind Kenntnisse in Analysis, Linearer Algebra sowie Kenntnisse einer höheren Programmiersprache.


Kontakt



Büro

Name

Konsultationen

Raum

Telefon

E-Mail

Büro an der TU Berlin:

Martin Grötschel

nach Absprache

Raum: MA 302

314-23266

Bitte unter: groetschelzib.de

Büro am Zuse-Institut (ZIB):

Martin Grötschel

nach Absprache

Raum: 3025

84185-210

groetschelBeschreibung:
                  C:\Users\groetsch\Desktop\klammeraffe.gifzib.de

Büro am Zuse-Institut (ZIB):

Axel Werner

nach Absprache

Raum: 3035

84185-356

wernerzib.de

Büro an der TU

Torsten Klug

nach Absprache

Raum: MA 307

314 28323

klugzib.de   


Tutor: Benedikt Bodendorf


bodendor@math.tu-berlin.de

Literatur Beschreibung: (down)

Hier sind einige ausgewählte Vorschläge für Literatur zur Linearen und Kombinatorischen Optimierung sowie Graphentheorie:

Ahuja R.K., Magnanti T. L., Orlin J.B.: Network flows: theory, algorithms, and applications, Prentice Hall, 1993.
Bertsimas D., Robert Weismantel R.: Optimization Over Integers, 2005.
Bixby R.: Solving real-world linear programs: A decade and more of progress. In: Operations Research, Band 50, Nr. 1, 2002, S. 3–15.
Chvatal, V.: Linear Programming, Freeman, 1983
Dantzig, George B.: Lineare Programmierung und Erweiterungen. Springer-Verlag, 1966.
Diestel R.: Graph Theory, Second Edition, Springer, 2000.
Gritzmann P.: Grundlagen der Mathematischen Optimierung, Springer Spektrum, 2013
M. Grötschel M., Lovász, L, Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Springer, 1988.
Jungnickel D.: Graphs, Networks and Algorithms, Series: Algorithms and Computation in Mathematics, Volume 5, fourth edition, Springer, 2013
Bernhard Korte, Jens Vygen: Combinatorial Optimization Theory and Algorithms, Springer, 2000 - 2012.
Krumke S.O., Noltemeier H.: Graphentheoretische Konzepte und Algorithmen, Teubner, 2006.
Matousek J., Gärtner B.: Using and Understanding Linear Programming, Springer, 2006.
Nemhauser G.L., Wolsey L.A.: Integer and Combinatorial Optimization, Wiley, 1999.
Padberg M.: Linear Optimization and Extensions, Springer, 1995.
Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity, 1998.
Schrijver A.: Theory of Linear and Integer Programming, Wiley, 1998.
Vanderbei R.J.: Linear Programming, Springer, 2001.


Zusatzinformationen Beschreibung: (down)

Für die Vorlesung gibt es 10 Punkte (gemäß ECTS).

Kriterien für einen wissenschaftlichen Abschluss:
Es werden insgesamt 14 Zettel mit Übungsaufgaben verteilt. Es müssen jeweils mindestens 50 % der Übungspunkte der ersten und zweiten Serie von 7 Übungsaufgabenzetteln erworben werden.

Abschlussprüfung:
Als Abschlussprüfung zur Vorlesung ADM I findet am 12. Februar 2015 (ab 16:15 Uhr im Hörsaal MA 043) eine schriftliche Klausur statt.
Zusätzlich wird eine Nachklausur am 10. April 2015 um 10 Uhr angeboten (s.u.).
Aufgrund der großen Anzahl von Hörern sind mündliche Einzelprüfungen zeitlich nicht durchführbar.

Die Klausureinsicht findet am Montag, dem 23.02.2015 von 10 bis 12 Uhr im Raum MA315 statt.


Die Nachklausur findet am 10. April 2015 (ab 10:15 Uhr im Hörsaal MA 041) statt.
Die Anmeldung zur Klausur ist online über QISPOS möglich.

Erste Vorankündigung:
Zur Vorlesung ADM II im Sommersemester 2015 findet analog eine Klausur am Semesterende statt.


Letzte Änderung: 10. März 2015