Geometric Integer Programming

Main content

Lecturer Assistant Lecture Exercise
Prof. Dr. Robert Weismantel

Jörg Bader,

Kevin Zemmer

Thu 13-15

HG G 26.3

Wed 11-12

HG F 26.3

Short description

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.

Prerequisites

"Mathematical Optimization" (401-3901-00L).

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.

Exercises

The weekly exercise sheets for Geometric Integer Programming can be found at the following moodle course:
https://moodle-app2.let.ethz.ch/course/view.php?id=2006
All information on the course can be found there. The moodle course is regularly updated and may also be accessed as a guest.

Bibliography

- Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas 2005,
- Schrijver: Theory of linear and integer programming, Wiley, 1986.

Grading

The final exam is oral.

 

 
 
Page URL: https://www.math.ethz.ch/ifor/education/courses/spring-2016/geometric-integer-programming.html
Fri Jul 28 00:34:05 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich