Diskrete Optimierung (M03)

Wintersemester 2014/15

Vorlesung: C. Helmberg

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.

This time, 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.

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