Hi all, I have been pointed to the discussion some time ago. You could be interested in the approach implemented in FuncDesigner LP model: http://openopt.org/NumericalOptimizationForFuncDesignerModels#LP_example Maybe in future I'll add FuncDesigner examples for MILP and some more classes.
Let me also note - statement "COIN-OR and CPLEX which have similar performances" is completely wrong. First of all COIN-OR project is a set of solvers (LP, NLP, etc), not an LP/MILP solver. At second, it is well-known CPLEX is too far ahead of any free MILP solver. See for example the bench by Hans Mittelmann (one of most authoritative), where CPLEX is 6 times faster of fastest free MILP solver http://forum.openopt.org/viewtopic.php?id=18 Regards, D. On Jun 29, 2:08 pm, 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 > Programshttp://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 --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an 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 -~----------~----~----~----~------~----~------~--~---
