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:
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?)
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
This is not really a full solution to your problem, but I think it may help or at least give you some ideas.
Your requirement that the solutions be integer makes this an NP problem. If we first consider the relaxation of the problem so that the domain is the real numbers, you are asking to solve the satisfiability problem of 0 <= A*c <= 1, where A is a matrix and c is your vector of unknowns. This is a standard linear program (LP with trivial objective), and can be solved efficiently (in polynomial time). You may want to use this as a first pass test to determine feasibility since if the relaxed LP has no solutions, your integer LP certainly has no solutions. A good LP solver will also return a feasible point if possible, and you may be able to round the vector's entries to find an integer solution.
As others have mentioned, if you wanted to maximize a linear objective function based on these constraints then you would have an integer linear programming problem, for which no efficient general solution exists. Instead you seem to be asking for the number of points in the feasible region, which is a different problem, but it too is complicated by having to have integer solutions.
The best idea I can come up with involves finding the points on the boundary of the feasible region, and using those to determine the number of points inside. This works well at accelerating "count the lattice points" type problems in lower dimensions, but the boundary is still just one dimension smaller than the volume in question. If your problem gets over a few dimensions then the problem will still be intractable, even if it is faster than enumerating all the solutions.