Counting solutions to linear inequalities [closed]

Question

I am trying to solve a problem which I have reduced down to counting the number of integer solutions to a number of linear inequalities. I need to be able to count the number of solutions for any number of variables c_1, ..., c_n, but for n=3 the equations could be written as:

The equations. http://silicon.appspot.com/readdoc?id=155604

Now, I know the values of n and r in advance and wish to find the number of (c_1, ..., c_n) solutions that exist.

Can this be done efficiently (faster than enumerating the solutions)? (If so: how?; if not: why?)

Answer 1

To solve this problem I would probably go into the realms of constraint programming. It seems like you have a classic all different constraint (a bit like the N-Queens problem). Have a go at one of the free constraint solvers listed below. That will give you a solution quite efficiently. It'll basically generate the whole search tree but with the nice All-Different constraint implementations out there, the tree will end up being pruned almost to nothing.

http://www.gecode.org/ http://minion.sourceforge.net/ http://jacop.osolpro.com/ http://research.microsoft.com/apps/pubs/default.aspx?id=64335

Here's the wikipedia list:
http://en.wikipedia.org/wiki/Constraint_programming#Constraint_programming_libraries_for_imperative_programming_languages