[SciPy-dev] small benchmark of LP solvers [from GSoC project]
Joachim Dahl
dahl.joachim@gmail....
Sun Jun 3 15:28:30 CDT 2007
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@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@scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/scipy-dev/attachments/20070603/3423421e/attachment.html
More information about the Scipy-dev
mailing list