Algorithm for finding integer solutions for linear inequalities

Question

Given $b_i,c_{i,j}\in \mathrm N^+, R_i(X_1,X_2,X_3,X_4)=\sum_jc_{i,j}X_j$ :

$0< R_1(x_1,x_2,x_3,x_4) < b_1$

$0< R_2(x_1,x_2,x_3,x_4) < b_2$

...

$0< R_n(x_1,x_2,x_3,x_4) < b_n$

Want to find all integer solutions with $0<x_1<x_2<x_3<x_4$

Is there a general algorithm to find integer solutions for these kind of inequalities?

Answer 1

You can use Integer (Linear) Programming with a constant objective function, i.e. $\mathbf{c} = \mathbf{0}$ (the ILP $\mathbf{c}$, not your $c$, of course). However, ILP is NP-hard, but if you have not more than a few hundred variables you should be fine with today's solvers.

I'm also not sure about finding all the solutions in the existing frameworks but this small paper is aimed to that task and it should be theoretically possible.

Answer 2

The following articles present an algorithm for describing the integer solutions of any system of linear equations and inequalities

https://link.springer.com/chapter/10.1007/978-3-319-66320-3_17 https://link.springer.com/chapter/10.1007/978-3-319-66320-3_18

This algorithm is implemented in Maple and the code can be obtained from the download page of the following web site

http://regularchains.org/

Section 2.6 of the documentation shows a few examples

http://regularchains.org/Documentation/Polyhedra_worksheet.pdf

As you can see, the integer points of the input polyhedron are decomposed into so-called Z-polyhedra. Each of those has at least one integer point and enjoys a natural "lifting" property: every integer point in a projection of that Z-polyhedron can be lifted to an integer point of that Z-polyhedron. In general, arbitrary polyhedra do not have that property.