The 2008 International Conference on Information Theory and Statistical Learning pages:53-59
Information-Theoretic Aspects of Integer-Point Enumeration in Polyhedra location:Las Vegas, Nevada date:July 2008
We describe the first implementation of the Barvinok--Woods
(2003) algorithm, which computes a short rational generating function for an
integer projection of the set of integer points in a polytope
in polynomial time, when the dimension is fixed.
The algorithm is based on Kannan's partitioning lemma
and the application of set operations to generating functions
that correspond to these sets.
We use a variant of the
recent strengthening of the partitioning lemma
due to Eisenbrand and Shmonin (2007) and provide several
algorithmic refinements to avoid performing redundant
The implementation has been done in
the second author's library.