For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer linear programming, but this has several disadvantages, like being forced to pick a component of the solution vector $x$ to maximize or minimize instead of just searching for a solution. The code I'm currently running is
p = MixedIntegerLinearProgram(maximization = True, solver = "GLPK")
x = p.new_variable(integer = True, nonnegative = True)
p.add_constraint( x*S == 0) #here the vector can be anything
p.add_constraint( x[25] <= 2020 )
p.set_objective( x[25] )
p.solve()
p.get_values(x)
Where $x[25]$ was chosen arbitrarily to make the mixed-integer linear program $p$ actually have a solution. Sometimes optimizing over $x[25]$ does not have a solution (or gives a solution after a very long time) while optimizing over another variable gives an almost instantaneous solution.
So my question. Is there a way to solve such systems without optimizing a specific component? (And if Sage Math isn't the best software to do this in please let me know and I'll give something else a try). If I must optimize over some condition, would it be possible to have my optimization be something more
uniform across all the variables, like picking a solution of minimal norm?
Is there any literature I could read on solving matrix equations in the non-negative integers? A simple search of MathSciNet didn't seem to find anything too relevant. Thanks for your thoughts!
