A. Barvinok (University of Michigan)

Title:
Generating Functions for Lattice Points
Abstract:
pdf file

G. Cornuéjols (Carnegie Mellon University)

Title:
Geometric Approaches to Cutting Plane Theory
Abstract:
In this course, we discuss cutting planes for mixed integer linear programs. We give a geometric understanding for several of the classical cutting planes such as split cuts, Gomory mixed integer cuts and intersection cuts, and we discuss the relationships between these various families. These connections are then used to generate better cutting planes from a computational point of view.

F. Eisenbrand (MaxPlanckInstitut)

Title:
Fast Algorithms for Integer Programming in Fixed Dimension
Abstract:
pdf file

J. de Loera (University of California, Davis)

Title 1:
Experimenting and Applying the Rational Function Method: A LattE Tutorial
Abstract 1:
We will introduce the audience to the software LattE and implementation of Barvinok's algorithm and some of its applications to Integer Programming and Combinatorics.
Title 2:
Transportation Polytopes: Structure, Algorithms, and Applications to Optimization and Statistics
Abstract 2:
Transportation problems are among the first ever studied in combinatorial optimization (e.g. assignment problems, bipartite matching problems,etc). The structure of the associated polyhedra attracted attention early on from mathematicians. In the first of two 2hourlong lectures. I will review of the properties of the classical 2way transportation polytopes (e.g. total unimodularity of equations, diameter, maximum number of vertices, etc). The second lecture will introduce to their lessknown relatives, the multiway transportation polytopes. We will sketch a proof of the recent result of the speaker and Shmuel Onn showing these simple polyhedra contain in fact all rational convex polytopes. This has very interesting consequence to integer programming and statistics.

R. Weismantel (OttovonGuericke Univ. Magdeburg)

Title:
The Integral Basis Method and Extensions
Abstract:
The course is concerned with questions related to the geometry of integer programs. It is shown that from the concept of integral generating sets (a subsets of integer points of a given set that span every integer point in the set with respect to nonnegative integer combinations), a theory of integer programming emerges that connects with (i) the total dual integrality of a system of linear inequalities, (ii) the theory of cutting planes, (iii) the derivation of optimality conditions for a feasible point. Once the importance of integral generating sets has become clear, we will focus on an algorithm that makes use of those sets. The core of the method is a reformulation technique that allows to replace subsets of original variables by other new variables. In this way the problem is embedded in a new space. We will discuss practical issues as well as extensions to mixed integer and nonlinear integer programming.

