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
optimization.
Copyright. All Rights Reserved.