<p>Check out</p>

<p><a href="https://www.math.ucdavis.edu/~latte/">https://www.math.ucdavis.edu/~latte/</a></p>

<p>and the corresponding paper</p>

<p>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.</p>

<p>The algorithm they implement was introduced in </p>

<p>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.</p>

CC BY-SA 3.0
2014-04-25T21:33:28.107Z
2014-04-25T21:33:28.107Z
Rahul Savani
<p>As far as I know, the <em>parameterized complexity</em> of the counting problem is still open. It is known that <em>ILP solving</em> is fixed-parameter tractable in the number of variables ('Integer programming with a fixed number of variables', H.W.Lenstra Jr), although <em>ILP solution counting</em> is expected to be $\# W[1]$-hard. The question was first asked by N. Betzler if my memory is correct.</p>

CC BY-SA 3.0
2014-04-26T13:57:26.370Z
2014-04-26T15:10:29.797Z
2014-04-26T15:10:29.797Z
NisaiVloot
<p>Beside Latte, there is a less famous tool, called Barvinok (name of the original author of the algorithm):
<a href="http://freecode.com/projects/barvinok" rel="nofollow">http://freecode.com/projects/barvinok</a></p>

<p>The algorithm is described in this paper:  </p>

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

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

CC BY-SA 3.0
2014-04-26T06:47:07.573Z
2014-04-26T06:47:07.573Z
sean
<p>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? </p>

<p>Update: dimension of the space is $n$ and is a variable in the problem. </p>

CC BY-SA 3.0
2014-04-26T01:10:19.740Z
Maybe you know this, but let me mention that it's NP-hard because the IP feasibility problem is NP-hard.
Sasho Nikolov
CC BY-SA 3.0
2014-04-26T18:12:33.227Z
I think counting the solutions is #P-complete. You can encode the permanent of a 0-1 matrix as such a problem.
Thomas Steinke
<approximation-algorithms><polytope>
The number of integral points in a polytope
Daniel
# The number of integral points in a polytope

(Asked by: username_0 on 2014-04-25)

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.

**Tags:** approximation-algorithms, polytope

> **Comments:**
> **username_1**: Maybe you know this, but let me mention that it's NP-hard because the IP feasibility problem is NP-hard.  
> **username_2**: I think counting the solutions is #P-complete. You can encode the permanent of a 0-1 matrix as such a problem.  

---

## 3 answers

### Answer by username_3 on 2014-04-25. Score: 6

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.


---

### Answer by username_4 on 2014-04-26. Score: 4

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.


---

### Answer by username_5 on 2014-04-26. Score: 3

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.


---

