Since the OP's problem has no inequalities (such as requiring that all integers in question are non-negative), it is solved by using Hermite normal form.
If A is an m by n integer matrix, the Hermite normal form of A is an upper triangular integer matrix H (also m by n), along with an m by m integer matrix of determinant 1 (i.e. it's invertible) so that H = U A. So the original equation A x = b becomes (after multiplying by U): H x = U b, for which it's easy to get the general solution (just back solve. If you ever get a non-integer by dividing there are no solutions). Since U is invertible, multiplying the equation by U doesn't introduce spurious solutions. Victor On Friday, September 14, 2012 5:46:01 AM UTC-4, Nathann Cohen wrote: > > Helloooooooooooooo !!! > > To consider the problem as linear program and use >> MixedIntegerLinearProgram() with integer constrains works, but it is very >> very slow for larger systems. >> > > Well, your problem is *precisely* what Integer Linear Program solvers are > written for, so I guess that using them is the good way to go unless you > plan on using some properties of the matrices you generate (and that the LP > solvers would not notice) to solve your equation. > > They are indeed slow in some cases, but we have to work with the tools > available, or rather those we know about. ILP's what I would try to do > myself -- if you find some other way to solve these equations please let me > know, for I use them very often and I would be delighted to solve my graph > problems faster too :-) > > By the way, in Sage MixedIntegerLinearProgram uses GLPK by default to > solve these problems, but you can also ask it to solve them with Gurobi or > CPLEX, which are usually *MUCH* faster. > > Good luuuuuuuuuck ! :-) > > Nathann > -- 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.
