Forschungsinstitut für Diskrete Mathematik

Vorlesung "Lineare und Ganzzahlige Optimierung"

Sommersemester 2022

Die Vorlesung am 7.7.2022 muss leider ausfallen. Stattdessen wird es am 14.7. noch eine Vorlesung geben, deren Inhalt aber nicht mehr prüfungsrelevant ist.
Unfortunately, the LGO lecture on July 7 has to be cancelled. Instead, there will be another lecture on July 14, but the content is not relevant to the exam.

Prüfungen:

Termine: 1. Runde: 18.7. - 22.7.; 2. Runde: 22./23.9., jeweils im Konferenzraum, Lennéstr. 2

Am Dienstag, den 5.7. wurden in der Vorlesung Prüfungstermine mit den anwesenden Hörern abgesprochen. Die Liste mit den Terminen wird auch am 12.7. noch einmal ausgelegt. Die Terminzuordnung per E-Mail erfolgt wir folgt: Es gibt sieben Zeitfenster:

Mo, 18.7., 13:35-18:45
Di, 19.7., 9:15-12:05
Di, 19.7., 14:10-18:20
Mi, 20.7., 9:15-12:05
Mi, 20.7., 14:45-15:45
Do, 21.7., 9:15-12:05
Do, 21.7., 14:10-18:20

Bitte schreiben Sie mir ([email protected]) bis Freitag, 8.7., 14 Uhr, zu welchen Terminen Sie keine Zeit haben (wenn Sie denn nicht immer Zeit haben). Am Freitag werden ich dann eine Zuordnung finden und Ihnen einen Termin mitteilen, den Sie mir wiederum kurz bestätigen sollten.

Nachprüfung: Für die Nachprüfung gibt es 4 Zeitfenster:

Do, 22.9.2022, 9:15-12:05
Do, 22.9.2022, 13:00-18:20
Fr, 23.9.2022, 9:15-12:05
Fr, 23.9.2022, 13:00-18:20

Bitte schreiben Sie mir ([email protected]) bis Montag, 8.8., zu welchen Terminen Sie keine Zeit haben (wenn Sie denn nicht immer Zeit haben). Bis Donnerstag, 11.8., werden ich dann eine Zuordnung finden und Ihnen einen Termin mitteilen, den Sie mir wiederum kurz bestätigen sollten.

Zulassungskriterien:

Regelmäßige Übungsteilnahme
Mindestens einmaliges Vorführen eine Lösung
Mindestens 50% der erreichbaren Gesamtpunktzahl

Exams:

Dates: First round: 7/18 - 7/22; second round: 9/22 and 9/23.

Admission criteria:

Regular participation in exercises
At least one presentation of a solution
At least 50% of the total achievable points

Link zur eCampus-Seite/Link to ecampus web page

Vorlesungsskript/Lecture notes

Folien/Slides:

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 write this in your registration for the exercise classes. 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: Di, Do 16-18

Übungen: Zweistündig, nach Vereinbarung

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

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. 3. Auflage, Springer, 2018.
A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986.
R.J. Vanderbei, Linear Programming: Foundations and Extentions, Kluwer Academic Publishers, Dordrecht, 5. Auflage, 2020.
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