Vorlesung Ganzzahlige Optimierung - Theorie und Algorithmen
Dozent:
Prof. Dr. R. Schrader
Zeit und Ort: Mi 8-9:30 und Fr 9:30-11 (bitte die geänderte Zeit am Freitag beachten)
Seminarraum Weyertal 80
Vorlesungsbeginn am 14.4.2010
Inhalt der Vorlesung
Die ganzzahlige Optimierung beschäftigt sich mit Optimierungsproblemen, in denen einige der
Variablen nur ganzzahlige Werte annehmen dürfen. Die Vorlesung wird verschiedene theoretische und algorithmische Aspekte der ganzzahligen Optimierung behandeln:
Polyeder, Relaxierungen (LP, semidefinite, Lagrange), Optimierung und Separation,
dynamische Programmierung, Branch & Bound, Schnittebenenverfahren, Spaltengenerierungsverfahren.
Die Vorlesung wird 4-stündig mit Übungen
(2-stündig) angeboten. Ein Schein kann durch Teilnahme an den Übungen
und eine Abschlussklausur
erworben werden.
Literatur
- B. Korte und J. Vygen, Combinatorial Optimization, Springer
- G.L. Nemhauser und L.A. Wolsey, Integer and combinatorial optimization, John Wiley & Sons, 1999
- A. Schrijver, Theory of linear and integer programming, John Wiley & Sons, 1986
- A. Schrijver, Combinatorial optimization: Polyhedra and efficiency, Springer, 2003
- L.A. Wolsey, Integer programming, John Wiley and Sons, 1998
- U. Faigle, W. Kern, G. Stiller, Algorithmic Principles of Mathematical Programming, Kluwer, 2002
Übungen
In den Übungen wird der Inhalt der Vorlesung
vertieft und es besteht die Möglichkeit, den Vorlesungsstoff zu diskutieren. Zusätzlich
werden in den Übungen die Aufgaben besprochen und es wird eine intensive
Prüfungsvorbereitung stattfinden.
