Geometric Integer Programming
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.
The purpose of the lecture is to provide a geometric treatment of the theory of integer optimization.
"Mathematical Optimization" (401-3901-00L).
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.
The weekly exercise sheets for Geometric Integer Programming can be found at the following moodle course:
All information on the course can be found there. The moodle course is regularly updated and may also be accessed as a guest.
- Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005,
- Schrijver: Theory of linear and integer programming, Wiley, 1986.
The final exam is oral.