\(\mathbb N\)-solutions to linear systems over \(\mathbb Z\) (Q1827486)

The authors propose and compare two algorithms for computing \(\mathbb N\)-solutions to linear systems over \(\mathbb Z\). This problem is known to be NP-complete. The first algorithm uses Gröbner bases, the second uses linear programming methods. The main result of the paper is bases on the fact that the general \(\mathbb N\)-solution to a linear system over \(\mathbb Z\) can be computed by using any method for computing a particular \(\mathbb N\)-solution. This conclusion comes from the fact that the authors reduce the computation of the minimal \(\mathbb N\)-solutions or vertices, to determining a particular solution of the given system, and particular solutions of a finite number of new systems where some variables have been fixed. The reduction consists of a recursive process.