Integer Linear Programming (ADM III), SS 2009

LV-Nr.:

When and Where:

There will be no lectures in the upcomming week (01.07.09 and 03.07.09). But there will be a tutorial on 01.07.09 at 10:15 in MA 649.

Overview:

Integer linear programs (IP) are a powerful concept in applied mathematics. Most combinatorial optimization problems can be modeled by an IP. Though integer linear programming is hard in general, the mathematical understanding of IPs has led both to highly useful, general solvers and polynomial time algorithms for large abstract classes of IPs. At the basis of these achievements lies an elegant mathematical theory. This theory is the subject of the lecture.

Among the topics covered are Hilbert Basis, Lattice Polytopes, Unimodularity, Total Dual Integrality, Chvatal Closure, and Polymatroids.

Prerequisite:

The lecture is intended for advanced students of mathematics or computer science. The presentation builds on the courses ADM I and in particular ADM II (Linear Programming).

Exercises:

Exercise sessions will take place every second week on Wednesday, 12:30 - 14:00 in MA 542. Assignment sheets will be published in the week before the exercise.

Literature:

Contact: