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.

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

3 Answers 3


Check out


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.