[sage-support] Re: integer linear programming in Sage?
Dear John,
On Oct 8, 10:01 pm, John H Palmieri <[EMAIL PROTECTED]> wrote:
...
> This may be a silly question, but integer linear programming seems to
> be about maximizing some quantity relative to constraints given by a
> matrix equality (or inequality), where everything is happening over
> the integers. How does this relate to finding integer solutions to a
> matrix equation?
Certainly I am not expert for ILP, but I did some applications of ILP
in 3-dimensional topology. And in that application, ILP always was
about finding non-negative integer solutions of a linear system of
equalities with integer coefficients.
So, nothing about "maximizing".
Actually this is a major building block for Wolfgang Haken's theory of
normal surfaces, and thus for certain classification algorithms for a
large class of closed 3-manifolds.
> I find myself wanting to do something similar: find *all* solutions to
> Ax = b, where A, x, and b have non-negative integer entries. I'm
> trying to figure out if the various responses here will help me. In
> the situation of interest to me, I know that there are only finitely
> many solutions, and I know one solution.
In the above-mentioned application, you would have b=0, and then there
are *finitely* many non-neg integer solutions ("fundamental"
solutions) that additively generate all non-neg integer solutions. And
IIRC, for finding the fundamental solutions, you need to detect the
smallest integer points on the edges of the cone of non-negative
solutions to the equation - so, this indeed involves optimisation.
However, it seems that the problem you are interested in is classical
as well, and therefore I suspect you find a solution in
A. Schrijver:
Theory of linear and integer programming.
Wiley-Interscience, Chichester 1986.
Given the various applications, it would be great to have high-
performance ILP in Sage!
Yours
Simon
--~--~-~--~~~---~--~~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
On Oct 7, 11:38 am, Paul Zimmermann <[EMAIL PROTECTED]> wrote: > Hi, > > a question of a colleague from my lab: > > can Sage solve linear systems A*x=b, where A is a matrix with positive > integer coefficients, b is a vector with positive integer coefficients, > and the unknown vector x is searched over the positive integers? > > I guess this is more or less equivalent to integer linear programming (ILP), > see http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns. This may be a silly question, but integer linear programming seems to be about maximizing some quantity relative to constraints given by a matrix equality (or inequality), where everything is happening over the integers. How does this relate to finding integer solutions to a matrix equation? I find myself wanting to do something similar: find *all* solutions to Ax = b, where A, x, and b have non-negative integer entries. I'm trying to figure out if the various responses here will help me. In the situation of interest to me, I know that there are only finitely many solutions, and I know one solution. John --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
On Wednesday 08 October 2008, Marshall Hampton wrote:
> Martin - is that already accessible in sage or would some sort of
> wrapper have to be written?
Here are the Singular examples done with Sage:
sage: singular.LIB("intprog.lib")
1. call with single right-hand vector
sage: A = matrix(ZZ, 2, 3, [1,1,0,0,1,1])
sage: b1 = vector(ZZ,[1,1])
sage: c = vector(ZZ,[2,2,1])
sage: singular.eval('intmat A[2][3]=%s'%str(A.list())[1:-1]) # todo make this
nicer
sage: A = singular("A")
sage: b1 = singular(str(b1.list())[1:-1],'intvec'); # todo make this nicer
sage: c = singular(str(c.list())[1:-1],'intvec'); # todo make this nicer
sage: print singular.solve_IP(A,b1,c,'"pct"')
0,
1,
0
2. call with list of right-hand vectors
sage: b2 = vector(ZZ,[-1,1])
sage: b2 = singular(str(b2.list())[1:-1],'intvec'); # todo make this nicer
sage: #l = singular.list([b1,2]) # bug in singular.list function
sage: l = singular("%s,%s"%(b1.name(),b2.name()),"list")
sage: print singular.solve_IP(A,l,c,'"ct"')
[1]:
0,1,0
[2]:
not solvable
3. call with single initial solution vector
sage: singular.eval('intmat A[2][3]=2,1,-1,-1,1,2') # todo make this nicer
sage: A = singular("A")
sage: b1 = singular("3,4,5",'intvec'); # todo make this nicer
sage: singular.solve_IP(A,b1,c,'"du"')
0,
7,
2
4. call with single initial solution vector and algorithm needing a positive
row space vector
sage: singular.solve_IP(A,b1,c,'"hs"')
0
5. call with single initial solution vector and positive row space vector
sage: prsv = singular('1,2,1','intvec')
sage: singular.solve_IP(A,b1,c,'"hs"',prsv);
0,
7,
2
6. call with list of initial solution vectors and positive row space vector
sage: b2 = singular('7,8,0','intvec')
sage: l = singular("%s,%s"%(b1.name(),b2.name()),"list")
sage: singular.solve_IP(A,l,c,'"blr"',prsv);
[1]:
0,7,2
[2]:
7,8,0
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: [EMAIL PROTECTED]
--~--~-~--~~~---~--~~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
Martin - is that already accessible in sage or would some sort of wrapper have to be written? > > Is this what you are looking for: > > http://www.singular.uni-kl.de/Manual/3-0-4/sing_610.htm > > ? > > Cheers, > Martin > > -- > name: Martin Albrecht > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _www:http://www.informatik.uni-bremen.de/~malb > _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
I have created a spkg to install lp_solve into Sage; it can be obtained at: http://www.math.unl.edu/~shartke2/files/lp_solve-5.5.0.13.spkg I have posted to sage-devel suggesting this spkg for inclusion into Sage. lp_solve includes a linear programming solver (simplex based) and an integer programming solver (branch and bound). The IP solver is strong enough to solve problems up to about 100 variables (give or take, depending on the problem). lp_solve comes with Python bindings, and their online documentation is very clear. GLPK also has 2 sets of nice Python bindings: python-glpk at http://www.dcc.fc.up.pt/~jpp/code/python-glpk/ and PyGLPK at http://www.cs.cornell.edu/~tomf/pyglpk/ PyGLPK was just updated to work with the latest version of GLPK. I believe that work is ongoing to make python-glpk compile with the very latest version of GLPK. I hope to make a spkg for GPLK and these Python bindings at some point, though seeing how this semester is going, it's probably not going to be anytime soon. Best wishes, Stephen --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
On Tuesday 07 October 2008, Paul Zimmermann wrote: >Hi, > > a question of a colleague from my lab: > > can Sage solve linear systems A*x=b, where A is a matrix with positive > integer coefficients, b is a vector with positive integer coefficients, > and the unknown vector x is searched over the positive integers? > > I guess this is more or less equivalent to integer linear programming > (ILP), see > http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns. Is this what you are looking for: http://www.singular.uni-kl.de/Manual/3-0-4/sing_610.htm ? Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
On Oct 7, 8:38 pm, Paul Zimmermann <[EMAIL PROTECTED]> wrote: > a question of a colleague from my lab: > ... integer linear programming (ILP) I'm not sure either, but he could try his luck with openopt: http://scipy.org/scipy/scikits/wiki/MILP interfacing with lpsolve or glpk. h --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-support] Re: integer linear programming in Sage?
I believe that the answer is currently: no, Sage cannot do integer linear programming. But I could be wrong, if that capability is hiding in something added since the last time this question came up. I am not sure what open source code is out there to do that - ? M. Hampton On Oct 7, 12:38 pm, Paul Zimmermann <[EMAIL PROTECTED]> wrote: >Hi, > > a question of a colleague from my lab: > > can Sage solve linear systems A*x=b, where A is a matrix with positive > integer coefficients, b is a vector with positive integer coefficients, > and the unknown vector x is searched over the positive integers? > > I guess this is more or less equivalent to integer linear programming (ILP), > seehttp://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns. > > Paul Zimmermann --~--~-~--~~~---~--~~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
