TOMLAB OPTIMIZATION LOGO TOMLAB OPTIMIZATION AREA top banner
  # LOGIN   # REGISTER (FREE TRIAL)
  # myTOMLAB  

Tomlab v3.1 Performance

Linear programming

Tomlab v3.1 was tested against the Optimization Toolbox 2.1 on a large set of dense linear programming problems, with n variables, m inequality constraints.
Five groups with twenty problems each were randomly generated. The spread for (n,m) was ±25. The mean values are shown in the table, one row for each group.
The objective function values were sampled in [-10,0], linear constraint matrix in [0,10] and right hand side in [0,10*n].

The table shows the mean CPU time used.

The clear choice for dense problems is the LPOPT solver, which is more than 2000 times faster than the simplex solver in Optimization Toolbox 2.1, and more than 1000 times faster than the LIPSOL interior point solver in Optimization Toolbox 2.1.

The other sparse Tomlab solvers are also order of magnitude faster than the solvers in Optimization Toolbox 2.1.
 

n m Tomlab 3.1 Optimization Toolbox 2.1
    SQOPT lpSolve MINOS LPOPT linprog-simplex linprog-lipsol
    MEX MATLAB MEX MEX MATLAB MEX
206 149 0.07 0.75 0.11 0.02 9.42 7.31
308 200 0.13 1.36 0.18 0.02 29.92 19.97
402 243 0.19 4.15 0.26 0.03 62.51 39.20
503 243 0.25 3.00 0.34 0.05 118.84 55.74
1008 547 1.00 19.19 1.41 0.18 949.26 522.37

A test was made on three LP examples that are part of the Optimization Toolbox 2.1 distribution.
The picture is the same as for the tests above.
MINOS is the choice for large LP problems, other choices are SQOPT and SNOPT.
 

n Eq/Ineq Tomlab 3.0 Optimization Toolbox 2.1 MAT-FILE NAME
    SQOPT SNOPT MINOS LPOPT linprog-simplex linprog-lipsol  
    MEX MEX MEX MEX dense MATLAB MEX  
1677 627/0 1.25 1.22 0.85 --- --- 7.69 densecolumns
1000 100/0 0.36 0.30 0.09 0.48 13.14 1.06 browneq
48 30/20 0.06 0.09 0.09 0.34 12.70 0.33 sc50b

Quadratic programming

The results for some of the Tomlab v3.1 solvers was compared with the Optimization Toolbox 2.1 solvers
on three user supplied quadratic programming problems.
Times are in seconds. All Tomlab solvers are order of magnitude faster than the Opt Tbx solvers.

Variables Constraints Tomlab 3.0 Optimization Toolbox 2.1 Company
  Equalities Inequalities LSSOL QPOPT MINOS(QP) QLD QUADPROG QP  
177 4 4 0.19 0.89 0.29 0.41 16.66 16.94 Morningstar.com
64 0 1172 0.22 0.22 0.56 0.09 1.08 1.38 Supélec, France
224 0 2252 0.20 0.66 0.77 0.36 1.11 5.14 Supélec, France

Tomlab v3.1 was tested against the Optimization Toolbox 2.1 on a the unconstrained quadratic problem that is part of the Optimization Toolbox 2.1 distribution.
The Tomlab QPOPT solver is 27 times faster than QUADPROG using default values.
The Tomlab LSSOL solver is 57 times faster than QUADPROG using default values.
 

Variables Tomlab 3.0 Optimization Toolbox 2.1 MAT-FILE NAME
  SQOPT QPOPT QLD LSSOL QUADPROG  
400 0.43 0.19 0.69 0.09 5.16 qpbox1

Constrained Optimization Example - Robot problem

Test on industrial ill-conditioned robot problem with quadratic objective function.
The problem has 12 simply-bounded variables and six quadratic constraints with lower and upper bounds, trying to maximize the following function (from Nonlinear maximation for ABB Robotics project):

f = x(1:6)' * B * x(1:6) + mass_vector * x(7:12) + gravity

x(1:6) is the angle speed of each axis, x(7:12) is the angle acceleration of each axis

Tomlab conSolve and nlpSolve take advantage of second-order information, which in this case is trivially supplied.
The QP solver used for conSolve and nlpSolve is MINOS in QP version.

The Tomlab NPSOL solver is more than 100 times faster than fmincon using default values.
 
 

Description Tomlab 3.0 OPTTB 2.1
  npsol nlpSolve conSolve fmincon
Function and gradient evaluations 12/11 11/11 3/3 2401/171
Iterations  7 10 3 170
Elapsed time in seconds 0.05 0.31 0.08 5.94
Maximal reduced gradient 1E-15 1E-15 1E-15 7E-5

The accuracy of the supplied solution from fmincon is not good, because 11
out of 12 reduced gradient values are large (ideally zero).
All reduced gradient values around the machine accuracy indicates that
all Tomlab solvers have found the correct minimum.

Mixed-Integer Programming

The Tomlab solver mipSolve implements a general branch and bound algorithm for mixed-integer programs. When dual feasible solutions are available, mipSolve is using the Tomlab dual simplex solver DualSolve to solve subproblems, which is significantly faster than using an ordinary linear programming solver, like the Tomlab lpSolve.

In v3.1 and /SOL v3.1, running MINOS as subproblem solver gives increased speed.

mipSolve also implements user defined priorities for variable selection, and different tree search strategies.
For 0/1 - knapsack problems a round down primal heuristic is included.

The following test on the number of iterations (nodes visited) for mipSolve, shows how much the result is influenced by using priorities and
the round-down heuristic on three standard test problems for 0/1 - knapsack problems (Weingarter 1, Hansen Plateau 1, PB 4).
The priority vector is set to the objective function coefficients (lowest value gives highest priority).
The last columns show results using the Tomlab /Xpress toolbox, running the state-of-the-art MIP solver XpressMP Release 12 with default options and using cuts.

  Iterations (nodes visited)
Knapsacks/
Variables
Heuristic+
Priorities 
Priorities  Heuristic Standard XpressMP
No cuts
XpressMP
Use cuts
2/28 94  470  142 896  130 50
4/28 76 130 788 1088 67 67
2/29 208 1228 822 3038 73 73

Tests on two Generalized Assignment Problems (GAPs) gave the following results, comparing mipSolve with the state-of-the-art MIP solver XpressMP Release 12 with default options, using cuts and both using presolve and cuts. The time difference is clear for these more difficult integer programming problems. mipSolve finds the optimal solution, but takes a lot of time to go through the whole tree to prove the optimality.

n m mipSolve XpressMP
    Depth first, then breadth search Standard Using cuts Presolve and cuts
    Nodes Seconds Nodes Seconds Nodes Seconds Nodes Seconds
55 15 > 10000 > 279 1637 0.421 464 0.282 323 0.219
55 15 > 10000 > 311 829 0.250 9 0.125 47 0.265

Bookmark this web site for future reference


    Tomlab © 1989-2022. All rights reserved.    Last updated: Oct 3, 2022. Site map. Privacy Policy