DE EN
Forschungsinstitut für
Diskrete Mathematik
Menü

Vorlesung "Lineare und Ganzzahlige Optimierung"

← Semesterübersicht

Sommersemester 2020

Wegen des Coronavirus wird die Vorlesung mindestens zu Beginn als präsenzfreie Veranstaltung durchgeführt. Vorlesungen und Übungen werden online als zoom-Meetings stattfinden. Alle angemeldeten Teilnehmer haben für die Vorlesung eine Einladung per E-Mail erhalten. Wer teilnehmen will, aber noch keine Einladung hat, möge sich per E-Mail (brenner(at)dm.uni-bonn.de) melden.

Prüfungen

  • Es wird mündliche Prüfungen geben, die überwiegend in vom 27.7. bis zum 31.7. durchgeführt werden. Im Einzelfall können Prüfungstermine außerhalb dieses Zeitraums abgesprochen werden.
  • Die Prüfungen finden als Präsenzprüfungen im Konferenzraum des Forschungsinstituts für Diskrete Mathematik, Lennéstr. 2 statt. Hier finden Sie ''Handreichungen für Studierende'' zum Thema Präsenzprüfungen.
  • Die 2. Prüfungen finden im Zeitraum vom 21.9. bis zum 25.9. statt.
  • Die Anmeldung zu den einzelnen Terminen der 1. Prüfung erfolgt am dem 9.7. per E-Mail (s.u.).

Vergabe von Prüfungsterminen:

  • In den folgenden Zeiträumen finden Prüfungen statt:
    1. Mo, 27.7., 13:00 - 19:30
    2. Di, 28.7., 9:00 - 13:00
    3. Di, 28.7., 13:00 - 19:30
    4. Mi, 29.7., 9:00 - 13:00
    5. Mi, 29.7., 13:00 - 19:30
    6. Do, 30.7., 9:00 - 13:00
    7. Do, 30.7., 13:00 - 19:30
    8. Fr, 31.7., 9:00 - 13:00
    9. Fr, 31.7., 13:00 - 19:30
    10. Mo, 3.8., 9:00 - 13:00
    11. Mo, 3.8., 13:00 - 19:30
  • Wer nicht zu allen diesen Terminen Zeit hat, kann Terminwünsche zu äußern, indem er bis zum Ende des 10. Juli eine E-Mail an "brenner (at) dm.uni-bonn.de" schreibt. Betreff der E-Mail muss "LGO" sein. Die E-Mail muss inbesondere eine Zeile enthalten, die mit folgendem Text beginnt:
    Ich habe zu folgenden Terminen keine Zeit:
    Danach müssen in der Zeile Zahlen von 1 bis 11 stehen (getrennt durch Leerzeichen), die aus obiger Liste die Nummern der nicht in Frage kommenden Termine enthält. Bitte geben Sie nur die Zahlen an, keine Zeiten und Daten.
  • Jeder zur Prüfung angemeldete Teilnehmer erhält bis zum Ende des 13. Juli eine E-Mail mit einem Prüfungstermin, den er bitte möglichst umgehend bestätigt. Diese Terminvergabe erfolgt unter dem Vorbehalt, dass der Teilnehmer zur Prüfung zugelassen ist. Verbindliche Auskunft über die Zulassung gibt nur das BASIS-System bzw. das Bachelor-Master-Büro.

Aktuelle Informationen zu den Regelungen und Empfehlungen bezüglich der Coronavirus-Epidemie finden Sie auf den Seiten des Bachelor-Master-Büros Mathematik und der Universität Bonn

Kommentierte Folien der Vorlesungen:

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.

The lessons of this lecture course start on April, 21 but it is recommended to have a look into the first chapter of the lecture notes before the lessons start.

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: Es wird mündliche Prüfungen geben.

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