On counting integral points in a convex rational polytope

Given a convex rational polytope $\Omega(b):=\{x\in\R^n_+\,|\,Ax=b\}$, we consider the function $b\mapsto f(b)$, which counts the nonnegative integral points of $\Omega(b)$. A closed form expression of its $\Z$-transform $z\mapsto \mathcal{F}(z)$ is easily obtained so that $f(b)$ can be computed as the inverse $\Z$-transform of $\mathcal{F}$. We then provide two variants of an inversion algorithm. As a by-product, one of the algorithms provides the Ehrhart polynomial of a convex integer polytope $\Omega$. We also provide an alternative that avoids the complex integration of $\mathcal{F}(z)$ and whose main computational effort is to solve a linear system. This latter approach is particularly attractive for relatively small values of $m$, where $m$ is the number of nontrivial constraints (or rows of $A$)


Math. Oper. Res. 28 (2003), pp. 853--870.