See the infosheet for detailed information on the format of the lecture:
Binder:
https://mybinder.org/v2/git/https%3A%2F%2Fgit.zib.de%2FRicardo%2Fopti2-notebooks.git/main
Diese Vorlesung führt in die ganzzahlige Optimierung ein.
Inhalt
Week 1 (Ganzzahlige Programmierungsprobleme): Einführung, Defnitionen, Beispiele, Totale Unimodularität
Week 2 (Branch-and-Bound): LP-Relaxierung, Baumsuche
Week 3 (Relaxierungen): Untere Schranken, Lagrange-Relaxierung
Woche 4 (Primalheuristiken): Eröffnungs- und Verbesserungsverfahren, Approximation, Beispiele
Woche 5 (Ganzzahlige Punkte in Rationalen Polyedern): Ganzzahlige Polyeder, Ganzzahlige Punkte in Rationalen Polyedren, Komplexität
Woche 6 (Schnittebenentheorie): Elementarer Abschluss, Rang
Woche 7 (Schnittebenenverfahren für IPs): Gomory-Schnitte 1. Art
Woche 8 (Schnittebenenverfahren für MIPs): Gomory-Schnitte 2. Art
Woche 9 (Polyedrische Kombinatorik): Matroid-Polytop
Woche 10 (Polyedrische Kombinatorik): Matching-Polytop
Woche 11 (Polyedrische Kombinatorik): TSP-Polytop
Woche 12 (Allgemeines Schnittebenenverfahren): Äquivalenz von Separierung und Optimierung
Woche 13 (Schnittebenenverfahren): Implementation (Tricks)
Week 14: Klausur
G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, Wiley 1988
L. Schrijver, Combinatorial Optimization, Springer 2003
B. Korte, J. Vygen, Combinatorial Optimization, Springer 2018
V. Chvátal, Linear Programming, Freeman 1983
Grundlagen
Diskrete Mathematik I und II
Videos
In Vbrick Rev via https://fu-berlin.eu.vbrickrev.com/#/playlist/fd62388d-d18c-45a8-9a98-30adb0dee4b4/videos/.
Begleitveranstaltungen
Ergänzend zur Übung wird eine zusätzliche integrierte Veranstaltung "Praktikum zur ganzzahligen Programmierung" angeboten. Dieser Kurs ist empfehlenswert, aber nicht zwinged notwendig für die Teilnahme an der Vorlesung.
| Course No | Course Type | Hours |
|---|---|---|
| 19215001 | Vorlesung | 2 |
| 19215002 | Übung | 2 |
| Time Span | 19.04.2022 - 11.10.2022 |
|---|---|
| Instructors |
Ralf Borndörfer
Ricardo Euler
Felix Maximilian Merz
|
| 0089c_MA120 | 2014, MSc Informatik (Mono), 120 LPs |
| 0280b_MA120 | 2011, MSc Mathematik (Mono), 120 LPs |
| 0280c_MA120 | 2018, MSc Mathematik (Mono), 120 LP |
| Day | Time | Location | Details |
|---|---|---|---|
| Tuesday | 12-14 | A6/SR 032 Seminarraum | 2022-04-19 - 2022-07-19 |