Vorlesung "Lineare und Ganzzahlige Optimierung"

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:

1. Mo, 18.7., 13:35-18:45
2. Di, 19.7., 9:15-12:05
3. Di, 19.7., 14:10-18:20
4. Mi, 20.7., 9:15-12:05
5. Mi, 20.7., 14:45-15:45
6. Do, 21.7., 9:15-12:05
7. Do, 21.7., 14:10-18:20

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

1. Do, 22.9.2022, 9:15-12:05
2. Do, 22.9.2022, 13:00-18:20
3. Fr, 23.9.2022, 9:15-12:05
4. Fr, 23.9.2022, 13:00-18:20

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

• 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

• 7.4.2022
• 12.4.2022
• 14.4.2022
• 19.4.2022
• 26.4.2022
• 28.4.2022
• 3.5.2022
• 5.5.2022
• 10.5.2022
• 12.5.2022
• 17.5.2022
• 19.5.2022
• 24.5.2022
• 31.5.2022
• 2.6.2022
• 14.6.2022
• 21.6.2022
• 23.6.2022
• 5.7.2022
• 12.7.2022
• 14.7.2022

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.

Dr. U. Brenner