TOMLAB Appendix G
Performance Tests on Linear Programming Solvers
We have made tests to compare the efficiency of different solvers on medium size LP problems. The solver lpSimplex, two algorithms implemented in the solver linprog from Optimization Toolbox 2.0 \[12\] and the Fortran solvers MINOS and QPOPT, available in TOMLAB v4.0, are compared. In all test cases the solvers converge to the same solution. The results are presented in five tables
Table 159, Table 160, Table 161, Table 162 and Table 163. The problem dimensions and all elements in (6) are chosen randomly. Since the simplex algorithm in linprog does not return the number of iterations as output, these figures could not be presented. lpSimplex has been run with two selection rules; Bland's cycling prevention rule and the minimum cost rule. The minimum cost rule is the obvious choice, because lpSimplex handles most cycling cases without problems, and also tests on cycling, and switches to Bland's rule in case of emergency (does not seem to occur). But it was interesting to see how much slower Bland's rule was.
The results in Table 159 show that problems with about 200 variables and 150 inequality constraints are solved by lpSimplex fast and efficient. When comparing elapsed computational time for 20 problems, it is clear that lpSimplex is much faster then the corresponding simplex algorithm implemented in the linprog solver. In fact lpSimplex, with the minimum cost selection rule, is more than five times faster, a remarkable difference. lpSimplex is also more than twice as fast as the other algorithm implemented in linprog, a primal-dual interior-point method aimed for large-scale problems \[12\]. There is a penalty about a factor of three to choose Bland's rule to prevent cycling in lpSimplex. The solvers written in Fortran, MINOS and QPOPT, of course run much faster, but the iteration count show that lpSimplex converges as fast as QPOPT and slightly better than MINOS. The speed-up is a factor of 35 when running QPOPT using the MEX-file interface.
In Table 160 a similar test is shown, running 20 problems with about 100 variables and 50 inequality constraints. The picture is the same, but the time difference, a factor of five, between lpSimplex and the Fortran solvers are not so striking for these lower dimensional problems. lpSimplex is now more than nine times faster than the simplex algorithm in linprog and twice as fast as the primal-dual interior-point method in linprog.
A similar test on larger dense problems, running 20 problems with about 500 variables and 240 inequality con- straints, shows no benefit in using the primal-dual interior-point method in linprog, see Table 163. In that test lpSimplex is more than five times faster, and 15 times faster than the simplex algorithm in linprog. Still it is about 35 times faster to use the MEX-file interfaces.
In conclusion, looking at the summary for all tables collected in Table 164, for dense problems the LP solvers in Optimization Toolbox offers no advantage compared to the TOMLAB solvers. It is clear that if speed is critical, the availability of Fortran solvers callable from Matlab using the MEX-file interfaces in TOMLAB v4.0 is very important.
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS | Minos | qpopt | linprog | linprog |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | ||
128 | 32 | 37 | 12 | 10 | 11 | 16 | 1.05 | 0.61 | 0.33 | 0.31 | 9.06 | 1.14 |
129 | 60 | 8 | 10 | 10 | 9 | 17 | 0.63 | 0.59 | 0.24 | 0.21 | 9.20 | 2.07 |
125 | 45 | 8 | 9 | 16 | 7 | 14 | 0.57 | 0.59 | 0.35 | 0.32 | 8.20 | 1.34 |
81 | 65 | 27 | 5 | 7 | 4 | 12 | 1.30 | 0.54 | 0.23 | 0.21 | 3.51 | 1.38 |
102 | 40 | 25 | 9 | 12 | 8 | 12 | 1.00 | 0.60 | 0.39 | 0.33 | 5.26 | 1.01 |
96 | 33 | 13 | 7 | 6 | 8 | 11 | 0.65 | 0.41 | 0.34 | 0.32 | 4.72 | 0.84 |
110 | 61 | 29 | 10 | 9 | 9 | 15 | 1.38 | 0.66 | 0.25 | 0.33 | 6.34 | 1.73 |
113 | 27 | 25 | 8 | 161 | 8 | 10 | 0.87 | 0.50 | 0.41 | 0.34 | 6.72 | 0.77 |
127 | 58 | 16 | 9 | 13 | 8 | 14 | 0.91 | 0.58 | 0.26 | 0.34 | 8.58 | 1.82 |
85 | 58 | 10 | 7 | 7 | 7 | 14 | 0.68 | 0.59 | 0.25 | 0.21 | 3.70 | 1.45 |
103 | 31 | 15 | 7 | 9 | 6 | 12 | 0.69 | 0.52 | 0.35 | 0.33 | 5.39 | 0.87 |
101 | 41 | 22 | 9 | 11 | 9 | 11 | 0.87 | 0.56 | 0.36 | 0.22 | 5.20 | 0.98 |
83 | 41 | 9 | 6 | 7 | 7 | 12 | 0.54 | 0.36 | 0.38 | 0.33 | 3.55 | 0.98 |
118 | 39 | 28 | 9 | 8 | 8 | 13 | 0.89 | 0.57 | 0.36 | 0.34 | 7.23 | 1.14 |
92 | 33 | 13 | 8 | 8 | 7 | 12 | 0.63 | 0.53 | 0.23 | 0.33 | 4.33 | 0.90 |
110 | 46 | 21 | 7 | 15 | 6 | 13 | 0.81 | 0.46 | 0.25 | 0.34 | 6.37 | 1.26 |
82 | 65 | 25 | 6 | 6 | 5 | 15 | 1.21 | 0.51 | 0.38 | 0.22 | 3.41 | 1.63 |
104 | 29 | 6 | 6 | 10 | 4 | 11 | 0.47 | 0.36 | 0.23 | 0.34 | 5.52 | 0.85 |
83 | 48 | 28 | 8 | 10 | 10 | 13 | 1.13 | 0.50 | 0.24 | 0.35 | 3.53 | 1.15 |
90 | 50 | 8 | 4 | 4 | 3 | 11 | 0.44 | 0.35 | 0.24 | 0.23 | 4.13 | 1.18 |
103 | 45 | 19 | 8 | 17 | 7 | 13 | 0.84 | 0.52 | 0.30 | 0.30 | 5.70 | 1.23 |
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS | Minos | qpopt | linprog | linprog | |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | |||
228 | 132 | 32 | 10 | 17 | 12 | 22 | 3.41 | 1.56 | 0.49 | 0.39 | 38.66 | 11.51 | |
191 | 164 | 20 | 9 | 9 | 10 | 18 | 3.12 | 1.85 | 0.49 | 0.26 | 24.91 | 12.50 | |
212 | 155 | 63 | 16 | 30 | 16 | 19 | 7.90 | 2.76 | 0.54 | 0.41 | 33.36 | 12.57 | |
185 | 158 | 53 | 25 | 16 | 16 | 18 | 6.86 | 4.00 | 0.38 | 0.43 | 23.88 | 11.29 | |
222 | 168 | 35 | 12 | 0 | 12 | 21 | 5.38 | 2.56 | 0.64 | 0.42 | 40.13 | 17.78 | |
207 | 162 | 10 | 8 | 6 | 7 | 21 | 1.91 | 1.69 | 0.51 | 0.27 | 33.74 | 15.66 | |
229 | 130 | 42 | 12 | 21 | 19 | 21 | 4.31 | 1.81 | 0.42 | 0.44 | 44.53 | 11.69 | |
213 | 136 | 56 | 6 | 21 | 6 | 19 | 6.02 | 1.19 | 0.51 | 0.39 | 36.54 | 11.07 | |
227 | 146 | 95 | 19 | 33 | 20 | 23 | 10.91 | 2.94 | 0.45 | 0.45 | 44.84 | 15.82 | |
192 | 150 | 25 | 6 | 13 | 5 | 16 | 3.22 | 1.26 | 0.53 | 0.27 | 27.07 | 10.79 | |
195 | 155 | 12 | 8 | 9 | 7 | 22 | 2.19 | 1.76 | 0.52 | 0.39 | 27.40 | 14.76 | |
221 | 160 | 30 | 12 | 10 | 11 | 22 | 4.66 | 2.41 | 0.59 | 0.43 | 36.95 | 18.00 | |
183 | 144 | 61 | 9 | 9 | 10 | 20 | 7.08 | 1.62 | 0.37 | 0.39 | 22.34 | 11.22 | |
200 | 165 | 19 | 10 | 0 | 14 | 19 | 3.27 | 2.22 | 0.61 | 0.42 | 27.94 | 14.43 | |
199 | 137 | 16 | 6 | 7 | 5 | 19 | 2.04 | 1.04 | 0.48 | 0.39 | 28.67 | 9.90 | |
188 | 154 | 18 | 8 | 9 | 7 | 17 | 2.59 | 1.57 | 0.53 | 0.39 | 25.19 | 10.81 | |
202 | 159 | 25 | 13 | 0 | 11 | 17 | 3.82 | 2.50 | 0.60 | 0.44 | 30.28 | 12.37 | |
223 | 155 | 103 | 16 | 20 | 17 | 24 | 12.50 | 2.95 | 0.56 | 0.44 | 39.54 | 18.06 | |
196 | 121 | 17 | 7 | 16 | 6 | 18 | 1.81 | 1.08 | 0.37 | 0.40 | 27.59 | 7.94 | |
202 | 133 | 47 | 10 | 12 | 12 | 20 | 4.71 | 1.34 | 0.38 | 0.41 | 30.03 | 10.09 | |
206 | 149 | 39 | 11 | 13 | 11 | 20 | 4.89 | 2.01 | 0.50 | 0.39 | 32.18 | 12.91 |
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS | Minos | qpopt | linprog | linprog |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | ||
328 | 192 | 174 | 26 | 33 | 34 | 24 | 34.73 | 6.59 | 0.70 | 0.76 | 121.57 | 50.52 |
326 | 212 | 65 | 10 | 24 | 12 | 20 | 14.67 | 3.28 | 0.82 | 0.57 | 116.00 | 49.87 |
325 | 185 | 15 | 15 | 33 | 15 | 33 | 4.19 | 4.31 | 0.78 | 0.55 | 112.43 | 63.63 |
327 | 186 | 21 | 11 | 14 | 13 | 26 | 4.49 | 2.86 | 0.75 | 0.55 | 112.95 | 49.85 |
327 | 192 | 22 | 6 | 8 | 6 | 19 | 5.01 | 1.92 | 0.73 | 0.48 | 113.05 | 40.58 |
285 | 181 | 9 | 7 | 11 | 7 | 21 | 2.33 | 1.98 | 0.64 | 0.44 | 80.13 | 30.33 |
323 | 219 | 24 | 10 | 15 | 11 | 22 | 6.44 | 3.39 | 0.88 | 0.56 | 110.42 | 59.27 |
284 | 201 | 45 | 10 | 10 | 9 | 24 | 9.46 | 3.21 | 0.71 | 0.35 | 81.13 | 44.80 |
285 | 199 | 22 | 9 | 14 | 8 | 21 | 4.85 | 2.62 | 0.71 | 0.33 | 78.64 | 39.07 |
296 | 228 | 33 | 11 | 10 | 13 | 23 | 9.00 | 3.78 | 0.77 | 0.39 | 89.67 | 59.23 |
310 | 185 | 28 | 14 | 19 | 16 | 25 | 5.62 | 3.30 | 0.73 | 0.54 | 96.93 | 43.75 |
311 | 219 | 23 | 12 | 12 | 17 | 22 | 6.53 | 4.13 | 0.78 | 0.60 | 97.05 | 53.90 |
280 | 206 | 58 | 23 | 28 | 17 | 20 | 12.20 | 5.80 | 0.76 | 0.40 | 75.66 | 38.22 |
319 | 204 | 17 | 11 | 11 | 12 | 23 | 4.41 | 3.45 | 0.64 | 0.54 | 106.16 | 52.84 |
287 | 202 | 8 | 6 | 6 | 5 | 17 | 2.43 | 1.79 | 0.75 | 0.34 | 78.26 | 32.93 |
328 | 202 | 44 | 9 | 11 | 10 | 18 | 9.32 | 2.72 | 0.76 | 0.53 | 117.09 | 41.86 |
307 | 213 | 85 | 12 | 34 | 12 | 30 | 19.35 | 3.97 | 0.86 | 0.51 | 98.97 | 70.47 |
285 | 199 | 29 | 11 | 11 | 9 | 24 | 6.43 | 3.27 | 0.71 | 0.47 | 78.32 | 44.30 |
315 | 194 | 22 | 10 | 8 | 9 | 20 | 5.14 | 3.00 | 0.73 | 0.52 | 102.28 | 41.73 |
310 | 181 | 38 | 6 | 7 | 5 | 22 | 6.95 | 1.80 | 0.71 | 0.46 | 96.99 | 36.93 |
308 | 200 | 39 | 11 | 16 | 12 | 23 | 8.68 | 3.36 | 0.75 | 0.50 | 98.18 | 47.20 |
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS | Minos | qpopt | linprog | linprog |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | ||
428 | 232 | 8 | 6 | 7 | 5 | 24 | 3.02 | 2.47 | 0.97 | 0.57 | 248.88 | 90.83 |
421 | 234 | 22 | 5 | 11 | 4 | 22 | 7.54 | 2.64 | 0.86 | 0.54 | 232.29 | 84.15 |
397 | 242 | 19 | 9 | 8 | 10 | 26 | 7.13 | 4.30 | 0.93 | 0.52 | 196.02 | 101.09 |
388 | 226 | 30 | 10 | 11 | 10 | 24 | 9.19 | 3.80 | 0.89 | 0.51 | 187.35 | 78.37 |
381 | 248 | 23 | 6 | 11 | 5 | 29 | 8.28 | 3.31 | 0.99 | 0.54 | 176.07 | 109.18 |
402 | 228 | 80 | 16 | 28 | 22 | 25 | 22.21 | 5.94 | 1.03 | 0.86 | 207.52 | 84.60 |
383 | 241 | 41 | 7 | 10 | 7 | 22 | 13.30 | 3.79 | 0.93 | 0.57 | 180.90 | 83.62 |
421 | 236 | 94 | 21 | 19 | 15 | 34 | 27.94 | 7.80 | 1.06 | 0.80 | 234.26 | 131.09 |
402 | 253 | 23 | 8 | 8 | 7 | 22 | 8.58 | 4.01 | 0.89 | 0.62 | 206.50 | 95.63 |
395 | 260 | 24 | 8 | 8 | 7 | 23 | 8.95 | 3.95 | 0.94 | 0.48 | 197.14 | 100.85 |
404 | 224 | 73 | 7 | 13 | 6 | 21 | 20.85 | 3.11 | 0.83 | 0.47 | 208.55 | 70.67 |
393 | 267 | 44 | 11 | 15 | 9 | 25 | 16.64 | 5.86 | 1.09 | 0.65 | 192.59 | 116.73 |
393 | 247 | 15 | 8 | 9 | 7 | 19 | 5.56 | 3.67 | 0.86 | 0.63 | 191.53 | 77.74 |
384 | 245 | 79 | 14 | 27 | 20 | 25 | 24.59 | 6.10 | 1.08 | 0.79 | 185.63 | 97.19 |
385 | 254 | 75 | 9 | 16 | 9 | 21 | 25.06 | 5.30 | 1.06 | 0.67 | 177.95 | 88.69 |
409 | 226 | 58 | 8 | 9 | 8 | 23 | 15.76 | 3.56 | 0.82 | 0.63 | 210.86 | 78.32 |
410 | 263 | 38 | 15 | 20 | 19 | 29 | 14.66 | 7.27 | 0.98 | 0.74 | 214.83 | 130.13 |
403 | 250 | 117 | 12 | 27 | 20 | 20 | 36.56 | 5.35 | 1.06 | 0.87 | 201.18 | 81.53 |
426 | 238 | 15 | 4 | 5 | 3 | 20 | 5.20 | 2.05 | 0.99 | 0.44 | 239.71 | 80.46 |
409 | 250 | 57 | 10 | 13 | 10 | 24 | 19.00 | 5.01 | 1.21 | 0.72 | 210.15 | 101.34 |
402 | 243 | 47 | 10 | 14 | 10 | 24 | 15.00 | 4.46 | 0.98 | 0.63 | 204.99 | 94.11 |
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS Minos | qpopt | linprog | linprog | |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | ||
528 | 232 | 35 | 7 | 7 | 6 | 28 | 12.33 | 3.50 | 1.28 | 0.86 | 453.03 | 124.19 |
482 | 252 | 33 | 9 | 7 | 8 | 25 | 12.02 | 4.26 | 1.00 | 0.71 | 346.37 | 120.24 |
503 | 251 | 72 | 15 | 38 | 17 | 35 | 25.45 | 6.79 | 1.49 | 1.01 | 387.91 | 170.35 |
507 | 259 | 142 | 18 | 46 | 27 | 28 | 50.68 | 8.55 | 1.43 | 1.33 | 397.67 | 147.41 |
487 | 240 | 48 | 17 | 33 | 19 | 26 | 16.69 | 7.02 | 1.29 | 1.03 | 346.64 | 114.96 |
506 | 251 | 46 | 8 | 11 | 8 | 24 | 16.92 | 4.19 | 1.13 | 0.78 | 394.38 | 119.71 |
504 | 256 | 35 | 9 | 16 | 8 | 36 | 14.73 | 4.97 | 1.26 | 0.81 | 395.37 | 183.20 |
489 | 255 | 36 | 28 | 27 | 28 | 26 | 14.39 | 11.87 | 1.32 | 1.30 | 355.66 | 129.45 |
514 | 228 | 9 | 4 | 4 | 3 | 32 | 3.24 | 1.80 | 1.05 | 0.51 | 399.44 | 133.82 |
524 | 245 | 64 | 11 | 27 | 14 | 28 | 21.99 | 5.34 | 1.26 | 1.00 | 439.31 | 135.32 |
506 | 255 | 112 | 22 | 28 | 23 | 23 | 40.12 | 10.07 | 1.12 | 1.21 | 385.12 | 117.49 |
497 | 224 | 50 | 11 | 14 | 12 | 31 | 15.51 | 4.57 | 1.11 | 0.86 | 362.38 | 121.94 |
482 | 249 | 27 | 16 | 17 | 20 | 30 | 10.24 | 6.75 | 1.15 | 1.08 | 339.27 | 138.16 |
485 | 249 | 18 | 6 | 21 | 5 | 20 | 6.36 | 2.87 | 1.35 | 0.55 | 340.35 | 95.15 |
509 | 223 | 84 | 22 | 35 | 17 | 35 | 23.51 | 7.55 | 1.17 | 1.04 | 390.88 | 142.31 |
0506 | 224 | 38 | 12 | 11 | 14 | 33 | 11.89 | 4.65 | 1.09 | 0.94 | 383.13 | 132.21 |
511 | 241 | 115 | 10 | 36 | 9 | 26 | 36.51 | 4.32 | 1.29 | 0.69 | 390.78 | 122.23 |
497 | 230 | 78 | 23 | 43 | 12 | 26 | 23.60 | 8.27 | 1.29 | 0.75 | 362.08 | 109.30 |
514 | 226 | 84 | 21 | 42 | 26 | 31 | 25.10 | 7.90 | 1.57 | 1.47 | 407.94 | 126.53 |
511 | 268 | 59 | 10 | 30 | 9 | 28 | 24.74 | 5.76 | 1.43 | 0.94 | 385.56 | 161.65 |
503 | 243 | 59 | 14 | 25 | 14 | 29 | 20.30 | 6.05 | 1.26 | 0.94 | 383.16 | 132.28 |
n | m | lpS | lpS | Minos | qpopt | linprog | lpS | lpS | Minos | qpopt | linprog | linprog |
Itb | Itm | Iter | Iter | Itl | Tb | Tm | Time | Time | Tm | Tl | ||
103 | 45 | 19 | 8 | 17 | 7 | 13 | 0.84 | 0.52 | 0.30 | 0.30 | 5.70 | 1.23 |
206 | 149 | 39 | 11 | 13 | 11 | 20 | 4.89 | 2.01 | 0.50 | 0.39 | 32.18 | 12.91 |
308 | 200 | 39 | 11 | 16 | 12 | 23 | 8.68 | 3.36 | 0.75 | 0.50 | 98.18 | 47.20 |
402 | 243 | 47 | 10 | 14 | 10 | 24 | 15.00 | 4.46 | 0.98 | 0.63 | 204.99 | 94.11 |
503 | 243 | 59 | 14 | 25 | 14 | 29 | 20.30 | 6.05 | 1.26 | 0.94 | 383.16 | 132.28 |