Forschungsinstitut für Diskrete Mathematik

Vorlesung "Lineare und Ganzzahlige Optimierung"

Sommersemester 2019

Diese Vorlesung eignet sich für das 4. oder 6. Semester im Rahmen des Bachelorstudiengangs Mathematik und ist eine Wahlpflichtvorlesung im Bereich C (Diskrete Mathematik). Ferner kann die Vorlesung im Rahmen des Bachelorstudiengangs Informatik besucht werden. Außerdem kann die Vorlesung für das Modul Foundations in Discrete Mathematics (F4C1) verwendet werden. Nähere Informationen können hier gefunden werden.

Remark for students of the Master's Program: I plan to give this lecture course in German. If you don't speak German but you are interested in the course, please attend the first lecture. We will see how many participants prefer English to German. In any case, there will be lecture notes in English and you can write your solutions to the weekly exercises in English. Also the final exam can be done in English.

Zeit und Ort: Di, Do 16-18, Gerhard-Konow-Hörsaal, Forschungsinstitut für Diskrete Mathematik, Lennéstr. 2

Übungen: Zweistündig, nach Vereinbarung

Prüfung: Erste Klausur am 15.7.2019 von 9-11 Uhr im Hörsaal 1, Endenicher Allee 19C. Bitte seien Sie schon 10 Minuten vor Beginn am Hörsaal, damit wir pünktlich um 9 Uhr s.t. anfangen können.
Klausureinsicht zur ersten Klausur: Freitag, 19.7., 13-14 Uhr (Buchstaben A-K) und 14-15 Uhr (Buchstaben L-Z) im Konferenzraum der Forschungsinstituts für Diskrete Mathematik, Lennéstr. 2.
Zweite Klausur am 21.9.2019 von 9-11 Uhr im Großen Hörsaal der Mathematik, Wegelerstr. 10. Auch diese Klausur beginnt 9 Uhr s.t.
Klausureinsicht zur zweiten Klausur: Freitag, 4.10., 15-16 Uhr im Konferenzraum der Forschungsinstituts für Diskrete Mathematik, Lennéstr. 2.

Ziele: Verständnis der grundlegenden Zusammenhänge der Polyedertheorie und der Theorie der linearen und ganzzahligen Optimierung. Kenntnis der wichtigsten Algorithmen, Fähigkeit zur geeigneten Modellierung praktischer Probleme als mathematische Optimierungsprobleme und deren Lösung, Computerimplementierung.

Inhalte: Modellierung von Optimierungsproblemen als (ganzzahlige) lineare Programme, Polyeder, Fourier-Motzkin-Elimination, Farkas' Lemma, Dualitätssätze, Simplexverfahren, Netzwerksimplex, Ellipsoidmethode, Bedingungen für Ganzzahligkeit von Polyedern, TDI-Systeme, vollständige Unimodularität, Schnittebenenverfahren.

Voraussetzungen: Lineare Algebra und Algorithmische Mathematik

Unterlagen zur Vorlesung:

Lecture notes (continuously updated).
Slides to the lecture course

Literaturhinweise:

V. Chvátal, Linear Programming, Freeman, New York, 1983.
M. Conforti, G. Cornuéjols, and G. Zambelli: Integer Programming, Springer, 2014.
B. Gärtner, J. Matousek, Understanding and Using Linear Programming, Springer, Berlin, 2006.
B. Korte, J. Vygen : Kombinatorische Optimierung: Theorie und Algorithmen. Springer, 2008.
A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986.
R.J. Vanderbei, Linear Programming: Foundations and Extentions, Kluwer Academic Publishers, Dordrecht, 1998.
L.A. Wolsey and G. Nemhauser: Integer and Combinatorial Optimization, Wiley-Interscience, 1988.

Alle genannten Bücher sind in der Bibliothek des Forschungsinstituts für Diskrete Mathematik vorhanden und auch ausleihbar.

Dr. U. Brenner