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.
Learning 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.
- 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.
Lecture notes
not available, blackboard presentation
Literature
Lecture notes will be provided.
Other helpful materials include
Bertsimas, Weismantel: Optimization over Integers, 2005
and
Schrijver: Theory of linear and integer programming, 1986.
Prerequisites / Notice
"Mathematical Optimization" (401-3901-00L)
Performance assessment
Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course