On counting integral points in a convex rational polytope

Jean B. Lasserre (lasserrelaas.fr)
Eduardo S. Zeron (eszeronmath.cinvestav.mx)

Abstract: 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$)

Keywords:

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Other )

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

Download:

Entry Submitted: 03/02/2003
Entry Accepted: 03/03/2003
Entry Last Modified: 10/05/2004

Modify/Update this entry