Matlab Linear Programming Benchmarks

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 [14] 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 35, Table 36, Table 37, Table 38 and Table 39. 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 35 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 [14]. 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.

Table 35: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. The last row shows the mean value of each column.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

In Table 36 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 .

Table 36: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. The last row shows the mean value of each column.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

Table 37: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. The last row shows the mean value of each column.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

Table 38: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. The last row shows the mean value of each column.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

A similar test on larger dense problems, running 20 problems with about 500 variables and 240 inequality constraints, shows no benefit in using the primal-dual interior-point method in linprog , see Table 39. 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.

Table 39: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. The last row shows the mean value of each column.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

506 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

In conclusion, looking at the summary for all tables collected in Table 40, 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.

Table 40: Computational results on randomly generated medium size LP problems for four different routines. Iter is the number of iterations and Time is the elapsed time in seconds on a Dell Latitude CPi 266XT running Matlab 5.3. The lpS solver is the TOMLAB lpSimplex, and it is run with both Bland's selection rule (iterations It_b, time T_b) and with the minimum cost selection rule (iterations It_m, time T_m). The linprog solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time T_m) and a large-scale primal-dual interior-point method (iterations It_l, time T_l). The number of variables, n, the number of inequality constraints, m, the objective function coefficients, the linear matrix and the right hand side are chosen randomly. Each row presents the mean of a test of 20 test problems with mean sizes shown in the first two columns.

n m lpS lpS Minos qpopt linprog lpS lpS Minos qpopt linprog linprog

It_b It_m Iter Iter It_l T_b T_m Time Time T_m T_l

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

« Previous « Start » Next »

n	m	lpS	lpS	Minos	qpopt	linprog	lpS	lpS	Minos	qpopt	linprog	linprog
		It_b	It_m	Iter	Iter	It_l	T_b	T_m	Time	Time	T_m	T_l
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