It may be a good idea to interface to OSI in order to avoid having to interface to both CPLEX and COIN-OR, but for license reasons we can not use OSI to interface to GLPK as OSI is GPL-Uncompatible and the only reason we want glpk installed by default is that it is the only gpl LP solver ;-)
Nathann On Jun 29, 3:09 pm, "Robert Schwarz" <m...@rschwarz.net> wrote: > 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<nathann.co...@gmail.com> > > 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 > > >> - CPLEXhttp://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 <m...@rschwarz.net> > > Get my public key athttp://rschwarz.net/key.asc --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
