Forschungsinstitut für Diskrete Mathematik

Vorlesung "Lineare und Ganzzahlige Optimierung"

Wintersemester 2017/17

Diese Vorlesung eignet sich für das (3. oder) 5. Semester im Rahmen des Bachelorstudiengangs Mathematik und ist eine Wahlpflichtvorlesung im Bereich C (Diskrete Mathematik). Außerdem kann die Vorlesung für das Modul Foundations in Discrete Mathematics (F4C1) verwendet werden. Ferner kann die Vorlesung im Rahmen des Bachelorstudiengangs Informatik besucht werden. Nähere Informationen können hier gefunden werden.

Zeit und Ort: Di, Do 12-14, Gerhard-Konow-Hörsaal, Forschungsinstitut für Diskrete Mathematik, Lennéstr. 2

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

The lecture will be held in English if non-german speaking students are present.

Goals: Understanding the relation between polyhedral theory and (integer) linear programming. Knowledge of the most important algorithms for linear and integer programming, ability to model practical problems.

Contents: Modelling optimization problems as (integer) linear programs, polyhedra, Fourier-Motzkin Elimination, Farkas' Lemma, duality, simplex algorithm, network simplex, ellipsoid method, interior point method, integrality conditions of polyhedra Polyedern, TDI systems, total unimodularity, cutting plane methods.

Prerequisites: Linear Algebra and Algorithmic Mathematics

Literatur:

A. Schrijver: Theory of Linear and Integer Programming, Wiley, New York, 1986.
V. Chvátal: Linear Programming, Freeman, New York, 1983.
B. Gärtner, J. Matousek: Understanding and Using Linear Programming, Springer, Berlin, 2006.
B. Korte, J. Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. Springer, 2008.
L.A. Wolsey and G. Nemhauser: Integer and Combinatorial Optimization, Wiley-Interscience, 1988.
M. Conforti, G. Cornuéjols, and G. Zambelli: Integer Programming, Springer, 2014.

Alle genannten Bücher sind in der Bibliothek des Forschungsinstituts für Diskrete Mathematik vorhanden und zum Teil auch ausleihbar.

Lecture notes can be found here.

Professor Dr. S. Held