Springe zum Hauptinhalt
Professur Algorithmische und Diskrete Mathematik
Algorithmische und Diskrete Mathematik

Diskrete Optimierung
(645,M03)

Sommersemester 2020

Vorlesung: Christoph Helmberg

Dienstag, 13:45-15:50, Raum C22.202 - 2/B202
Mittwoch, 11:00-12:30, Raum 2/W038
Bitte auf dieser OPAL-Seite anmelden.

LOGO

Kurzbeschreibung

Inhalt:

Optimierung über diskreten Grundmengen, Theorie und praktische Verfahren der linearen Optimierung mit Ganzzahligkeitsbedingungen, Relaxationen und duale Probleme, Lagrangerelaxation und Dekomposition, ganzzahlige Kegel und Polyeder, polynomial lösbare Probleme, ganzzahlige min-max-Resultate, Schnittebenenverfahren, semidefinite Relaxation, Approximationsalgorithmen.

If requested by at least one person, the course will be given in English:

Optimization over discrete ground sets, theory and practical methods of linear optimization with integrality constraints (linear integer programming), relaxations and dual problems, Lagrange relaxation and decomposition, integer cones and polyhedra, problems solvable in polynomial time, integer min-max results, cutting plane methods, semidefintie relaxation, approximation algorithms.

Corona-Mode: please visit the OPAL-course

Zielgruppe:

obl: M_FiMR2; wob: M_MaDI2, M_MaOW2, M_MaSF2, D_MaIn6, D_Ma__6, D_WM__6, M_FiAV2, M_FiBB2, M_FiFK2, M_FiIF2, M_FiUF2, M_In__2, M_In__4, D_InEM6, D_InEM8, M_MR__1; fak: M_MaNT2

Vorwissen:

Grundlagen der Optimierung, Grundlegende Begriffe der Graphentheorie

Here are introductory slides to the lecture series,
und hier die Folien zur Einführung in die Vorlesung auf deutsch.

Literatur

  • Cook, W. J., Cunningham, W.H., Pulleyblank, W. R., Schrijver, A.; Combinatorial Optimization; Wiley 1998

  • Groetschel, M., Lovasz, L., Schrijver, A.; Geometric Algorithms and Combinatorial Optimization, Springer 1988

  • Korte, B. und Vygen, J.; Combinatorial Optimization, Springer 2000

  • Schrijver, A.; Theory of Linear and Integer Programming; Wiley 1986

  • Schrijver, A.; Combinatorial Optimization; Springer 2003

  • Wolsey, L. A.; Integer Programming; Wiley 1998