Generating function methods in discrete optimization

Matthias Koeppe
University of California, Davis (UC Davis)

A. Barvinok (1994) pioneered an algorithmic theory of computing the exact number of lattice points of a given rational polytope. The method is based on his efficient version of the Khovanski-Pukhlikov-Lawrence theorem on rational-function-valued valuations that encode lattice-point sets of rational polyhedra as
generating functions. The encoding and all related algorithms are polynomial, whenever the dimension is a fixed constant.

In this tutorial, I present aspects of this algorithmic theory, including the necessary prerequisites from the algorithmic geometry of
numbers, and its applications in linear and nonlinear discrete

Presentation (PDF File)

Back to Optimization Tutorials