Let's consider a system of linear equations with integer coefficients:
n=3
m=5
A=random_matrix(ZZ,n,m)
b=random_vector(ZZ,n)
What is the best way to find an integer vector x such that Ax=b?
A rational solution is of course found by A.solve_right(b).
A random example:
A=matrix(ZZ,3,5,[-1, 0, -1, -1, 1, 0, -2, -1, 1, -8,-1, 0, 2, -8, -2])
b=vector(ZZ,3,[-1,-1,15])
A.solve_right(b) gives (-13/3, -13/6, 16/3, 0, 0), although there are
integer solutions,
e.g.: (-221, 13, 144, 65, -13)
Is there also a good way to get all integer solutions? In the example above
that would be something like:
[-10*t0 - 30*t1 - 221, -2*t0 + 3*t1 + 13, 7*t0 + 19*t1 + 144, 3*t0 + 9*t1 +
65, -2*t1 - 13]
for integer variables t0 and t1.
The best way I could think of is to implement the algorithm from section
4.5.2 from Knuth's TAOCP. (This is also where the solutions above come from)
Is there a simpler way to do that in sage?
Of course to we could formulate the same question in terms of linear
equations instead of matrices, but then solve() also gives rational,
non-integer solutions.
Maybe the right thing to use would be isolve from maple, but the interface
is broke ( see http://trac.sagemath.org/sage_trac/ticket/12295 ).
To consider the problem as linear program and use
MixedIntegerLinearProgram() with integer constrains works, but it is very
very slow for larger systems.
Any help will be appreciated,
moritz
--
You received this message because you are subscribed to the Google Groups
sage-support group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
