COIN-OR has a project called OSI, the open solver interface, for its own lp solver clp but also CPLEX and GLPK (among others, see: https://projects.coin-or.org/Osi/), so only this OSI has to be interfaced to SAGE, to get all generality in lp solving.
In my understanding, cbc can solve mixed-integer programs, but for the many combinatorial optimization problems (e.g. max cut in graphs) it's better to build your own sophisticated solver, using a framework like abacus or COIN-OR bcp. As for license issues: It shouldn't be a problem to write interface code, like there is with magma. Then the users would have to (optionally) install some COIN-OR projects on their own. There is already a list of useful software in the wiki: http://wiki.sagemath.org/optimization I would definitely be interested in some more code in this direction, especially together with the graph theory already available. On Mon, June 29, 2009 13:25, David Joyner wrote: > > Thanks for working on this! I agree with the points in your email. > > LP solvers are an important topic where I teach so I am happy to > help. I think some of my colleagues would be very interested in > trying out whatever is developed. I'm not an operations > research person myself but would be interested in testing out > any OR software interface you have. > > > > On Mon, Jun 29, 2009 at 7:08 AM, Nathann Cohen<[email protected]> > wrote: >> >> Hello everybody !!!! >> >> I have already sent a few messages about this and complained for a >> while. The only way for the moment to solve Linear Programs ( >> http://en.wikipedia.org/wiki/Linear_programming ) is CVXOPT, a library >> focused on convex optimization, and we need much, much more than this. >> >> There are three softwares that I know which can solve Linear >> Programs : >> >> - GLPK ( http://www.gnu.org/software/glpk/ ) >> http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit >> Totally Free, can be merged into SAGE >> >> >> - COIN-OR ( http://www.coin-or.org/ ) >> http://en.wikipedia.org/wiki/COIN-OR >> GPL-Uncompatible >> >> - CPLEX http://www.ilog.fr/products/cplex/ >> http://en.wikipedia.org/wiki/CPLEX >> Proprietary >> >> >> To my knowledge, GLPK is far behind COIN-OR and CPLEX which have >> similar performances. Now, GLPK is the natural choice for SAGE because >> it is totally Free, and it has to be available. But COIN-OR has such >> performances that it cannot be discarded just because of its license >> ( which is not "that far" from being GPL-Compatible, besides... ), and >> I think many of the persons using SAGE at work may have some access to >> CPLEX Licenses ( which lets them use it in parallel, or perhaps in a >> distributed way, I do not know all about it ). >> >> This, to say that all three should be accessible through SAGE ( GLPK >> by default, COIN-OR as an optionnal package, and CPLEX if installed ), >> and that we should begin to think about a common way to solve linear >> programs in SAGE, and as importantly MIP ( Mixed Integer Programs >> http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns >> ). >> I am particularly interested in this feature as it would mean that a >> ---LOT--- of new graph-theoretic functions could be very soon, very >> efficiently, and very easily added to the SAGE Library. We are missing >> so many essential things that could be solved in several lines of LP >> or MIP that waiting is just insane ;-) >> >> As I have my own constraints, I had to build for myself a quick >> interface between SAGE and CBC ( which belongs to the COIN-OR >> Family ). It uses the command-line executable and creates dirty >> temporary files, which we want to avoid in SAGE. In the end you can >> access COIN-OR through SAGE with two screens of code ( >> http://www-sop.inria.fr/members/Nathann.Cohen/cbc.spyx ), and a >> Maximum Independant Set becomes as easy as this : >> >> g=graphs.RandomGNP(10,.5) >> p=MIPSProgram(max=True) >> obj={} >> for i in g.vertices(): >> obj["V"+str(i)]=1 >> p.setinteger("V"+str(i)) >> >> p.setobj(obj) >> for (a,b,c) in g.edges(): >> obj={} >> obj["V"+str(a)]=1 >> obj["V"+str(b)]=1 >> obj["lt"]=1 >> p.addconstraint(obj) >> p.solve() >> >> I am sending this message because I would like to reach the people who >> would like to have LP and MIP solvers in SAGE, and who may be >> interested in writing the code we need for this. I would also like to >> have your advice about what I now imagine of its implementation. I >> would not like ( but this is only my advice, and "I am all ears" ) to >> have the user deal with the final matrices as we have to in CVXOPT. I >> like the idea of adding constraint independently from the previous >> ones as I am doing in this short code for Max Independant Set. It may >> not be the best way ( and please tell me what you think of it ) but I >> record each linear form : 2*A + 3*B - 5*C as a dictionary {"A":2, "B": >> 3, "C":-5 }. I have to add "lt":1 if I want to ensure that this form >> is < 1, but I think we should create a new class LinearConstraint with >> proper functions associated to it. Finally, the variable have no >> reason to be strings and should be general Object ( if possible ). >> >> I hope many of you will be interested by LP and MIP in Sage and will >> be willing to work on it too ! I have my version of it, so I can wait >> without any problem, but SAGE --needs-- LP and MIP solvers ;-) >> >> Have fun ! >> >> Nathann >> > >> > > > > -- Robert Schwarz <[email protected]> Get my public key at http://rschwarz.net/key.asc --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
