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
|