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.

- 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)