# The number of integral points in a polytope

Suppose we define a polytope with $$\mathbf{Ax} \leq \mathbf{b}$$ What is the best way to find/approximate the number of the integral points in the polytope? Update: how hard is the complexity of this problem?

Update: dimension of the space is $n$ and is a variable in the problem.

-
Maybe you know this, but let me mention that it's NP-hard because the IP feasibility problem is NP-hard. –  Sasho Nikolov Apr 26 at 1:10
I think counting the solutions is #P-complete. You can encode the permanent of a 0-1 matrix as such a problem. –  Thomas Apr 26 at 18:12

Check out

https://www.math.ucdavis.edu/~latte/

and the corresponding paper

Effective lattice point counting in rational convex polytopes. Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, Ruriko Yoshida. Journal of Symbolic Computation 2004 38:4, 1273-1302.

The algorithm they implement was introduced in

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Alexander I. Barvinok. Mathematics of Operations Research 1994 19:4, 769-779.

-

As far as I know, the parameterized complexity of the counting problem is still open. It is known that ILP solving is fixed-parameter tractable in the number of variables ('Integer programming with a fixed number of variables', H.W.Lenstra Jr), although ILP solution counting is expected to be $\# W[1]$-hard. The question was first asked by N. Betzler if my memory is correct.

-

Beside Latte, there is a less famous tool, called Barvinok (name of the original author of the algorithm): http://freecode.com/projects/barvinok

The algorithm is described in this paper:

Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vincent Loechner, Maurice Bruynooghe: Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions. Algorithmica 48(1): 37-66 (2007)

As far as I know, Latte can't handle parametric polytopes like Barvinok.

-