Title: Generating Functions for Lattice Points

Abstract:

pdf file

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.

Title: Fast Algorithms for Integer Programming in Fixed Dimension

Abstract:

pdf file

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 2-hour-long lectures. I will review of the properties of the classical 2-way transportation polytopes (e.g. total unimodularity of equations, diameter, maximum number of vertices, etc). The second lecture will introduce to their less-known relatives, the multi-way 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.

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.