|
Instructors: Dr. rer. nat. Andreas Paffenholz
Event type:
Lecture & Exercise
Org-unit: Dept. 04 - Mathematics
Displayed in timetable as:
Geom Combinatorics
Subject:
Crediting for:
Hours per week:
3
Language of instruction:
German and English
Min. | Max. participants:
- | -
Course Contents:
We will discuss the structure of lattices and lattice points in polyhedra, and their relation to discrete optimization from a geometric point of view.
Lattices are the set of integer linear combinations of a set of linearly independent vectors in some (finite dimensional) vector space. An important and well known example is the lattice Zn of integer points. The feasibility question in integer optimization asks whether a given polyhedron contains a point of this lattice.
The starting point in this lecture is the geometry of numbers. The fundamental theorems in this field consider conditions under which a convex body contains a point of the lattice. This area of research started with Minkowski's First Theorem stating that any centrally symmetric convex body of large enough volume contains an integer point. The algorithmic approach to this ask to find a lattice point in a polyhedron, if such a point exists. While this problem is known to be NP-complete in general, we will see that there is a polynomial time algorithm if the dimension is fixed. This is based on the computation of short vectors in lattices and the flatness theorem, which gives a universal bound (depending on the dimension) to the width of convex bodies without lattice points in the interior. We will also address the problem of counting lattice points in polyhedra, both from a geometric and algorithmic viewpoint. This will lead us to Ehrhart theory and, on the algorithmic side, to the polynomial time counting algorithm of Barvinok (again in fixed dimension).
Topics of the course will include
- Lattices and Polyhedra
- Geometry of Numbers, Minkowski’s and Blichfeldt’s theorems
- Lattice basis reduction and the LLL-algorithm
- the shortest vector problem
- integer programming in fixed dimension via Lenstra's algorithm
- Rational generating functions and Barvinok’s counting algorithm
If time permits we may, e.g., consider integer points in parametric polyhedra or cuts and lattice free polytopes.
Literature:
Dimitris Bertsimas und Robert Weismantel, Optimization over Integers, Dynamic Ideas, (2005).
Rekha Thomas, Lectures in geometric combinatorics, AMS (2005).
Alexander Barvinok, A Course in Convexity, AMS (2002)
Jesus De Loera, Raymond Hemmecke, Matthias Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM (2012)
Preconditions:
some knowlegde in Polyhedral Theory, Linear and Integer Programming, as, e.g., treated in the classes Introduction to Optimization and Discrete Optimization. Missing knowledge in these topics may be acquired in this class or in the tutorial.
Online Offerings:
moodle
|
