[GAP Forum] Non-negative solutions to linear Diophantine equations

[Nagy Gabor]

Hi Sven,

It seems that you have an integer linear programming (ILP) problem. 
Simple backtrack search will not bring you very far.

https://en.wikipedia.org/wiki/Integer_programming

Unfortunately, GAP has no LP or ILP solver. Thus, I suggest you to try 
SageMath (or Cocalc.com, which is basically the same). It has an 
extremely simple and intuitive interface to many great ILP solver software:

https://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html

Me personally, I like GLPK (since it is GPL) and Gurobi (performs good, 
with free academic license).

I hope this helps.

Cheers,

Gabor


On 2020. 12. 29. 13:30, Sven Reichard wrote:
> Dear Forum,
>
> I have a system Ax=b of linear Diophantine equations and I would like to find the set of all non-negative solutions x.
>
> This looks like a reasonable problem, but so far I have not found anything on it. My current solution works but not very efficiently. It does the following:
> - Lattice reduction on A
> - Find a rational solution x' (by SolutionMat)
> - Find an integral basis of the nullspace of A (by TriangulizedNullspaceMat)
> - Perform a backtrack search for non-negative integer solutions.
>
> If anybody could point me in the direction of other things to try I would be grateful.
>
> Best wishes for the New Year,
> Sven Reichard.
>
> Dresden International University
>
> _______________________________________________
> Forum mailing list
> Forum at gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum