[SciPy-dev] small benchmark of LP solvers [from GSoC project]

[Joachim Dahl]

If you use the native Python LP solver in CVXOPT for sparse problems, make
sure you
specify the matrices as sparse,  as this conversion is not done
automatically in the solvers.
I couldn't tell from your post what comparisons you're doing, but just in
case...

Joachim

On 6/1/07, dmitrey <openopt at ukr.net> wrote:
>
>  hi,
> for all who are interested:
> take a look at the puny benchmark of LP solvers available in my GSoC
> openopt module (provided CVXOPT with glpk and mosek is installed, as well as
> lp_solve).
> I shall try to connect the one to scikits during the next week (and switch
> for some weeks to other work, assigned to my GSoC milestones).
> 1st number is time elapsed (seconds), 2nd - cputime (opeopt bindings take
> less than 1-2% of the time)
>  LP name
> nVars
> nConstr
> density
> cvxopt_lp
> cvxopt_glpk
> cvxopt_mosek
> LPSolve
>
>
>
>
>
>
>
>
>
> LGPL
> GPL2
> non-free
> LGPL
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> trig
> 500
> 500
> 1
> 10.1/9.7
> 1.1/1.1
> N/A(2)
> 0.4/0.4
>
> trig
> 500
> 1000
> 1
> 16/15.9
> 3.5/3.4
> N/A(2)
> 0.76/0.72
>
> trig
> 1000
> 1000
> 1
> 99/98
> 6.8/6.7
> N/A(2)
> 1.67/1.64
>
> trig
> 1500
> 3000
> 1
> 479/470
> 177(1)/83
> N/A(2)
> 7.9/7.7
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> trig_sparse
> 500
> 500
> 0.1
> 0.39/0.38
> 0.39/0.38
> N/A(2)
> 0.16/0.17
>
> trig_sparse
> 500
> 1000
> 0.1
> 4.83/4.64
> 0.83/0.82
> N/A(2)
> 0.34/0.3
>
> trig_sparse
> 1000
> 1000
> 0.1
> 12.7/12.5
> 1.88/1.86
> N/A(2)
> 0.64/0.62
>
> trig_sparse
> 1500
> 3000
> 0.1
> 131/128
> 17.5(1)/12.3
> N/A(2)
> 3.91/3.81
>
>
>
> (1): swap encountered (I have 1 Gb)
> (2): internal mosek error (maybe problems with my AMD Athlon 64 3800+ X2)
>
> you should also take into account lb bounds used, it gives additional
> nVars constraints.
> some benchmarks of glpk are also available at
> http://plato.asu.edu/ftp/lpfree.html
> mosek is available at http://plato.asu.edu/ftp/lpcom.html
>
> all the solvers are available via single interface, let me paste data from
> the LP() doc (excuse my English):
>     LP: constructor for Linear Problem assignment
>     valid calls are:
>     p = LP(f, <params>)
>     p = LP(f=objFunVector, <params>)
>     p = LP(f, A=A, Aeq=Aeq, Awhole=Awhole, b=b, beq=beq, bwhole=bwhole,
> dwhole=dwhole, lb=lb, ub=ub)
>
>     NB! Constraints can be separated in many ways,
>     either AX <= b, Aeq X = beq (MATLAB-, CVXOPT- style),
>     or  Awhole X {< | = | >} bwhole  (glpk-, lp_solve- and many other
> software style),
>     or any mix of them
>
>     INPUTS:
>     f: size n x 1 vector
>     A: size m1 x n matrix, subjected to A * x <= b
>     Aeq: size m2 x n matrix, subjected to Aeq * x = beq
>     Awhole: size m3 x n matrix, subjected to Awhole * x { < | = | > }
> bwhole
>     b, beq, bwhole: corresponding vectors with lengthes m1, m2, m3
>     dwhole: vector of length m3 from {-1,0,1}, descriptor, sign of what
> (Awhole*x_opt - bwhole) should be equal to
>     (this will simplify translating from other languages to Python and
> reduce the amount of mistakes
>     as well as amount of additional code lines)
>
>     OUTPUT: OpenOpt LP class instance
>
>     Solving of LPs is performed via
>     r = p.solve(string_name_of_solver)
>     r.xf - desired solution (NaNs if a problem occured)
>     r.ff - objFun value (<f,x_opt>) (NaN if a problem occured)
>     (see also other fields, such as CPUTimeElapsed, TimeElapsed, etc)
>     Currently string_name_of_solver can be:
>     LPSolve (LGPL) - requires lpsolve + Python bindings installations (all
> mentioned is available in http://sourceforge.net/projects/lpsolve)
>     cvxopt_lp (GPL) - requires CVXOPT (http://abel.ee.ucla.edu/cvxopt)
>     cvxopt_glpk(GPL2) - requires CVXOPT(http://abel.ee.ucla.edu/cvxopt) &
> glpk (www.gnu.org/software/glpk)
>     cvxopt_mosek(commercial) - requires CVXOPT(
> http://abel.ee.ucla.edu/cvxopt) & mosek (www.mosek.com)
>
>     Example:
>     Let's concider the problem
>     15x1 + 8x2 + 80x3 -> min        (1)
>     subjected to
>     x1 + 2x2 + 3x3 <= 15              (2)
>     8x1 +  15x2 +  80x3 <= 80      (3)
>     8x1  + 80x2 + 15x3 <=150      (4)
>     100x1 +  10x2 + x3 >= 800     (5)
>     80x1 + 8x2 + 15x3 = 750         (6)
>     x1 + 10x2 + 100x3 = 80           (7)
>
>     Let's pass (2), (3) to A X <= b, (6) to Aeq X = beq
>     and rest of constraints will be handled via Awhole, bwhole, dwhole
>
>     array, list, matrix and real number are accepted:
>     f = array([15,8,80])
>     A = mat('1 2 3; 8 15 80')
>     b = [15, 80]
>     Aeq = mat('80 8 15')
>     beq = 750
>     Awhole = mat('8 80 15; 1 10 100; 100 10 1')
>     bwhole = array([150, 80, 800])
>     dwhole = [-1, 0, 1]
>     p = LP(f, A=A, Aeq=Aeq, Awhole=Awhole, b=b, beq=beq, bwhole=bwhole,
> dwhole=dwhole)
>     r = p.solve('LPSolve') #lp_solve must be installed
>     print 'objFunValue:', r.ff # should print 204.350288002
>     print 'x_opt:', r.xf
>
> There are also NLP, NSP classes available (currently unconstrained solvers
> ralg and ShorEllipsoid are supplied).
> LPSolve and glpk also provide MILP solvers, but cvxopt connection to glpk
> (that one is required) can't handle the integer indexes, so in my MILP class
> in nearest future  will be only one solver (LPSolve)
> I know that there is a software for connecting commercial LP/MILP/QP
> solver CPLEX to Python, but (at least currently)  I have no time for the
> one.
>
> I shall gladly take into account all your suggestions.
> Regards, Dmitrey.
>
>
>
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20070603/3423421e/attachment.html>