Vorlesung "Lineare und Ganzzahlige Optimierung"

Nachprüfung:

• Es wird Online-Prüfungen via Zoom geben, die vom 27.9. bis zum 29.9. durchgeführt werden.
• Wünsche für Prüfungstermine können per E-Mail geäußer werden (s.u.).

Vergabe von Prüfungsterminen:

• In den folgenden Zeiträumen finden Prüfungen statt:
  1. Mo, 27.9., 14:00 - 18:00
  2. Di, 28.9., 9:00 - 13:00
  3. Di, 28.9., 13:00 - 18:00
  4. Mi, 29.9., 14:00 - 18:00
• Wer nicht zu allen diesen Terminen Zeit hat, kann Terminwünsche zu äußern, indem er bis zum Ende des 8. September eine E-Mail an "brenner (at) or.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 4 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 10. September eine E-Mail mit einem Prüfungstermin, den er bitte möglichst umgehend bestätigt.

Second exams

• There will be online examinations via Zoom, most of which will be held from September 27 to September 29.
• Requests for examination dates can be made by e-mail (see below).

Allocation of examination dates:

• Examinations take place in the following periods:
  1. Mo, 27.9., 14:00 - 18:00
  2. Tu, 28.9., 9:00 - 13:00
  3. Tu, 28.9., 13:00 - 18:00
  4. We, 29.9., 14:00 - 18:00
• If you do not have time for all of these dates, you can make requests for dates by sending an e-mail to "brenner (at) or.uni-bonn.de" by the end of September 8. Subject of the e-mail must be "LGO". In particular, the e-mail must contain a line beginning with the following text:
  I do not have time on the following dates:
  After that, the line must contain numbers from 1 to 4 (separated by spaces), which contains the numbers of the ineligible dates from the above list. Please provide only the numbers, not times and dates.
• Each participant registered for the exam will receive an email by the end of September 10 with an exam date, please confirm as soon as possible.

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

Dr. U. Brenner