solving a matrix equation in the integers.

asked 2020-09-02 11:10:13 -0500

JRHales gravatar image

I'm trying to use sage to solve an expression of the form $xS = y$ for a fixed integer matrix $S$ and a fixed integer vector $y$. I need my solution vector $x$ to also have integer coefficients.

How I'm currently doing this is by using the mixed integer linear programming tool and my code looks something like this.

p = MixedIntegerLinearProgram(maximization = True, solver = "GLPK")
x = p.new_variable(integer = True, nonnegative = True)
p.add_constraint( x*S == y) #here the vector can be anything
p.add_constraint( x[25] <= 2020 )
p.set_objective( x[25] )
p.solve()
p.get_values(x)

The issue I have here is that the objective and the constraint are arbitrary and were just picked so that the space that the MixedIntegerLinearProgram function is trying to optimize over has a "feasable solution" (sage's words not mine). Is there a better way to find a solution to $xS = y$ in the integers (i.e a different function or package supported by sage) and if not, is there a way to have my constarint be to make the norm of the vector as small as possible (so that I'm not just artificially picking an entry to optimize my search over)?

edit retag flag offensive close merge delete