A Simple Algorithm for Counting Solutions to Integer Programs

Abstract

We consider the problem of counting solutions to integer linear programming problems of the form $\{x\in {\mathbb{Z}}_{\ge 0}^n:Ax=b\}$ where $A\in \{-\Delta ,\dots ,\Delta {\}}^{m\times n}$ and $b\in {\mathbb{Z}}^m$. We present an algorithm that counts solutions with $(n\Delta {)}^{m+o(1)}\cdot \log \Vert b\Vert$ arithmetic operations. This simplifies the algorithm of Gribanov and Malyshev, who considered the problem for the more general setting in which $A$ is $\Delta$-modular.