Java – find the set of integers where two linear equations hold

What algorithm can I use to find the set of all positive integer values of N1, N2,..., N7, where the following inequality holds

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, a set of N1 = 2, N2 = N3 =... = N7 = 0 holds the inequality How do I find all other value sets? Similar problems have been released in m.se

Added: I need to summarize the solution of n variables (which may be very large) What procedures can I apply for? For another specific 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,n7 >= 0,n8 >= 0

Python needs to be forever Wolfram Mathematica revealed that there were 4015 solutions in less than a 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,n3 >= 0,n4 >= 0,n5 >= 0,n6 >= 0,n8 >= 0},{n1,n3,n4,n5,n6,n7,n8},Integers]]

Solution

Reti43 has the right idea, but has a fast recursive solution with less restrictive assumptions about your inequality

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 will apply it to such a primitive problem,

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

For such a long-term problem, 6,7,3) solns8 = solve (smin, coef2) LEN (solns8) 4015

On my MacBook, both cases are completed in milliseconds This should be well extended to slightly larger problems, but fundamentally, it is O (2 ^ n) of coefficient n The degree of actual expansion depends on the size of the additional factor – a larger factor (smin compared to Smax -). The fewer solutions, the faster the operation

Update: from the discussion on linking m.se post, I see that the relationship between the two inequalities here is part of the problem structure In view of this, a slightly simpler solution can be given The following code also includes some additional optimizations to accelerate the 8-variable solution from 88 milliseconds to 34 milliseconds on my laptop I've tried an example of up to 22 variables and got the results in less than a minute, but it's never practical for hundreds of variables

def solve(smin,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 can apply it to such an 8 variable example,

solutions = solve(185,205,2))
len(solutions)
4015

The solution directly enumerates the lattice points in the bounded region Since you need all these solutions, the time required to acquire them will be proportional to the number of grid points bound (at most), which increases exponentially with the number of dimensions (variables)