find the set of integers for which two linear equalities holds true

Question

What algorithm can I use to find the set of all positive integer values of n1, n2, ... ,n7 for which the the following inequalities holds true.

97n1 + 89n2 + 42n3 + 20n4 + 16n5 + 11n6 + 2n7 - 185 > 0
-98n1 - 90n2 - 43n3 - 21n4 - 17n5 - 12n6 - 3n7 + 205 > 0
n1 >= 0, n2 >= 0, n3 >=0. n4 >=0, n5 >=0, n6 >=0, n7 >= 0

For example one set n1= 2, n2 = n3 = ... = n7 =0 makes the inequality true. How do I find out all other set of values? The similar question has been posted in M.SE.

ADDED:: I need to generalize the solution for n variables (might be large). What procedure can I apply? For another particular case n=8

97n1 + 89n2 + 42n3 + 20n4 + 16n5 + 11n6 + 6n7 + 2n8 - 185 > 0
-98n1 - 90n2 - 43n3 - 21n4 - 17n5 - 12n6  - 7 - 3n8 + 205 > 0
n1 >= 0, n2 >= 0, n3 >=0. n4 >=0, n5 >=0, n6 >=0, n7 >= 0, n8 >= 0

Python takes forever. Wolfram Mathematica reveals that there are 4015 solutions in less than minute.

Length[Solve[{97 n1 + 89 n2 + 42 n3 + 20 n4 + 16 n5 + 11 n6 + 6 n7 + 
     2 n8 - 185 > 0, 
   -98 n1 - 90 n2 - 43 n3 - 21 n4 - 17 n5 - 12 n6 - 7 n7 - 3 n8 + 
     205 > 0,
   n1 >= 0, n2 >= 0, n3 >= 0, n4 >= 0, n5 >= 0, n6 >= 0, n7 >= 0, 
   n8 >= 0}, {n1, n2, n3, n4, n5, n6, n7, n8}, Integers]]

Answer 1

Reti43 has the right idea, but there's a quick recursive solution that works with less restrictive assumptions about your inequalities.

def solve(smin, smax, coef1, coef2):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef1[i] * n[i] for i in range(len(coef1)]) > smin
    sum([coef2[i] * n[i] for i in range(len(coef1)]) < smax

    where coef1 and coef2 are equal-length lists of positive integers.
    """
    if smax < 0:
        return []

    n_max = ((smax-1) // coef2[0])
    solutions = []
    if len(coef1) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * coef1[0],
                                  smax - n0 * coef2[0], 
                                  coef1[1:], coef2[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // coef1[0]) + 1)
        for n0 in range(n_min, n_max + 1):
            if n0 * coef1[0] > smin and n0 * coef2[0] < smax:
                solutions.append([n0])
    return solutions

You'd apply this to your original problem like this,

smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 3)
solns7 = solve(smin, smax, coef1, coef2)
len(solns7)
1013

and to the longer problem like this,

smin, coef1 = 185, (97, 89, 42, 20, 16, 11, 6, 2)
smax, coef2 = 205, (98, 90, 43, 21, 17, 12, 7, 3)
solns8 = solve(smin, smax, coef1, coef2)
len(solns8)
4015

On my Macbook, both of these cases are solved in milliseconds. This should scale reasonably well to slightly larger problems, but fundamentally, it's O(2^N) in the number of coefficients N. How well it actually scales depends on how large the additional coefficients are - the more large coefficients (compared to smax-smin), the fewer possible solutions and the faster it'll run.

Updated: From the discussion on the linked M.SE post, I see that the relationship between the two inequalities here is part of the structure of the problem. Given that, a slightly simpler solution can be given. The code below also includes a couple of additional optimizations, which speed up the solution for the 8-variable case from 88 milliseconds to 34 milliseconds on my laptop. I've tried this on examples with as many as 22 variables and gotten the results in less than a minute, but it's never going to be practical for hundreds of variables.

def solve(smin, smax, coef):
    """
    Return a list of lists of non-negative integers `n` that satisfy
    the inequalities,

    sum([coef[i] * n[i] for i in range(len(coef)]) > smin
    sum([(coef[i]+1) * n[i] for i in range(len(coef)]) < smax

    where coef is a list of positive integer coefficients, ordered
    from highest to lowest.
    """
    if smax <= smin:
        return []
    if smin < 0 and smax <= coef[-1]+1:
        return [[0] * len(coef)]

    c0 = coef[0]
    c1 = c0 + 1
    n_max = ((smax-1) // c1)
    solutions = []
    if len(coef) > 1:
        for n0 in range(n_max + 1):
            for solution in solve(smin - n0 * c0,
                                  smax - n0 * c1, 
                                  coef[1:]):
                solutions.append([n0] + solution)
    else:
        n_min = max(0, (smin // c0) + 1)
        for n0 in range(n_min, n_max + 1):
            solutions.append([n0])
    return solutions

You'd apply it to the 8-variable example like this,

solutions = solve(185, 205, (97, 89, 42, 20, 16, 11, 6, 2))
len(solutions)
4015

This solution directly enumerates the lattice points in the bounded region. Since you want all of these solutions, the time it takes to get them is going to be proportional (at best) to the number of bound lattice points, which grows exponentially with the number of dimensions (variables).

Answer 2

In both examples you gave I noticed the same pattern. For example, for the first case if you add the two equations together, you'll get

-n1 - n2 - n3 - n4 - n5 - n6 - n7 + 20 > 0

which can be rearranged to

n1 + n2 + n3 + n4 + n5 + n6 + n7 < 20

This is a nice bounded equation that you can brute force. Specifically, you can iterate for n1 from 0 to 19, for n2 from 0 to 19-n1, etc. A possible solution of this would be (0, 0, 0, 0, 0, 0, 0), but we notice that this doesn't satisfy our original equation. So, just generate all possible values for (n1, n2, ..., n7) and keep only those which satisfy your equation. Hardcoding all this results to

def find_solutions(N):
    sols = []
    for n1 in xrange(N):
        for n2 in xrange(N-n1):
            for n3 in xrange(N-n1-n2):
                for n4 in xrange(N-n1-n2-n3):
                    for n5 in xrange(N-n1-n2-n3-n4):
                        for n6 in xrange(N-n1-n2-n3-n4-n5):
                            for n7 in xrange(N-n1-n2-n3-n4-n5-n6):
                                if (97*n1 + 89*n2 + 42*n3 + 20*n4 + 16*n5 + 11*n6 + 2*n7 - 185 > 0 and
                                    -98*n1 - 90*n2 - 43*n3 - 21*n4 - 17*n5 - 12*n6 - 3*n7 + 205 > 0):
                                    sols.append((n1, n2, n3, n4, n5, n6, n7))
return sols

find_solutions(20) finds all 1013 solutions in 0.6 seconds. Similarly, for the second case it finds all 4015 solutions in 2.3 seconds. Now, this isn't easy to generalise at all, but it shows that with a smart approach, Python or any other language, doesn't have to be slow.

On the other hand, recursion allows us to generalise this for any number of nested loops but at a price of running a bit slower.

def find_solutions(N, coeffs, depth=0, variables=None, subtotal=None, solutions=None):
    if variables is None:
        solutions = []
        subtotal = [0 for _ in xrange(len(coeffs[0]))]
        variables = [0 for _ in xrange(len(coeffs[0])-1)]
    if depth == len(coeffs[0])-2:
        for v in xrange(N-sum(variables[:depth])):
            conditions = all(
                subtotal[i]+coeffs[i][depth]*v > coeffs[i][-1]
                for i in xrange(len(coeffs))
            )
            if conditions:
                variables[depth] = v
                solutions.append(tuple(variables))
    else:
        for v in xrange(N-sum(variables[:depth])):
            variables[depth] = v
            total = [subtotal[i]+coeffs[i][depth]*v for i in xrange(len(coeffs))]
            find_solutions(N, coeffs, depth+1, variables, total, solutions)
    if depth == 0:
        return solutions

To run this, generate the coefficients for each equation and pass them to the function. Keep in mind the sign for the constants is inverted!

coeffs = [
    [97, 89, 42, 20, 16, 11, 2, 185],
    [-98, -90, -43, -21, -17, -12, -3, -205]
]
solutions = find_solutions(20, coeffs)
print(len(solutions))

This one finishes the n=7 case in 1.6 seconds and the n=8 case in 5.8. I'll look into any possible optimisations if you expect your n to get very large, but for the time being it looks satisfactory.

The remaining question is whether the sum of your equations will always simplify to something like n1 + n2 + ... nn < N. There is a simple solution around that if that's not the case, but I opted not to prematurely overgeneralise the code beyond the examples you had provided us.

Finally, I imagine the same approach could be implemented in Java or C# and it'd probably be even faster. I wouldn't mind doing that if your general cases are expected to take much longer to solve.