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 
linprogsimplex 
linproglipsol 


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 
MATFILE NAME 


SQOPT 
SNOPT 
MINOS 
LPOPT 
linprogsimplex 
linproglipsol 



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 
MATFILE 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 illconditioned robot problem with quadratic objective
function.
The problem has 12 simplybounded 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 secondorder 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 
1E15 
1E15 
1E15 
7E5 
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.
MixedInteger Programming
The Tomlab solver mipSolve implements a general branch and bound algorithm
for mixedinteger 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 rounddown
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
stateoftheart MIP solver
Xpress^{MP}
Release 12 with default options and using cuts.

Iterations (nodes visited) 
Knapsacks/
Variables 
Heuristic+
Priorities 
Priorities 
Heuristic 
Standard 
Xpress^{MP} No cuts 
Xpress^{MP} 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 stateoftheart MIP solver
Xpress^{MP}
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 
Xpress^{MP} 


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
