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.
Key topics are:
- Lattice theory and the polynomial time solvability of integer optimization problems in fixed dimension.
- Structural properties of integer sets that reveal other parameters affecting the complexity of integer problems
- Duality theory for integer optimization problems from the vantage point of lattice free sets.
not available, blackboard presentation
Lecture notes will be provided.
Other helpful materials include
Bertsimas, Weismantel: Optimization over Integers, 2005
Schrijver: Theory of linear and integer programming, 1986.
Prerequisites / Notice
"Mathematical Optimization" (401-3901-00L)
Performance assessment information (valid until the course unit is held again)