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@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
_______________________________________________
Forum mailing list
Forum@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
