Algebraic Methods in Integer Programming: A Survey
In the past decade, many new insights have been gained into the structure of integer programs via tools from computational and combinatorial commutative algebra. These results stem from a basic algorithm to solve integer programs using Groebner bases, discovered in the early nineties. Recent results of Barvinok and Woods have been used to show that these methods solve integer programs in polynomial time in fixed dimension. The algebraic methods touch on many different approaches to integer programming such as the traditional polyhedral methods based in linear programming, Scarf's approach via lattice-point-free polytopes and geometry of numbers, and basis reduction. They also relate to other branches of mathematics such as algebraic and symplectic geometry. In this talk, I will survey the highlights of this approach to integer programming and outline some of the open problems in this field.
Rekha Thomas, University of Washington
