401-3903-11L  Geometric Integer Programming

SemesterFrühjahrssemester 2016
DozierendeR. Weismantel
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch


KurzbeschreibungInteger programming is the task of minimizing a linear function over all the integer points in a polyhedron. This lecture introduces the key concepts of an algorithmic theory for solving such problems.
LernzielThe purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
InhaltKey topics are:
- lattice theory and the polynomial time solvability of integer optimization problems in fixed dimension,
- the theory of integral generating sets and its connection to totally dual integral systems,
- finite cutting plane algorithms based on lattices and integral generating sets.
Skriptnot available, blackboard presentation
LiteraturBertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005.
Schrijver: Theory of linear and integer programming, Wiley, 1986.
Voraussetzungen / Besonderes"Mathematical Optimization" (401-3901-00L)