Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
1  
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
add comment

3 Answers 3

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.