Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 '14 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 '14 at 18:12

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Beside Latte, there is a less famous tool, called Barvinok (name of the original author of the algorithm):

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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