Integer 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.
Objective
The purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
Content
Key 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.
Lecture notes
not available, blackboard presentation
Literature
Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005. Schrijver: Theory of linear and integer programming, Wiley, 1986.
Prerequisites / Notice
"Mathematical Optimization" (401-3901-00L)
Performance assessment
Performance assessment information (valid until the course unit is held again)