Elias at 14:57, 14 January 2012

2012-01-14T14:57:49Z

Elias at 11:55, 9 August 2011

2011-08-09T11:55:57Z

Elias: moved Users Guide Appendix G to TOMLAB Appendix G

2011-07-12T08:17:37Z

moved Users Guide Appendix G to TOMLAB Appendix G

← Older revision	Revision as of 03:17, 12 July 2011
(No difference)

Elias: Created page with "=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'', tw..."

2011-07-11T20:11:19Z

Created page with "=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'', tw..."

New page

=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.

{|
|+Table 159: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''is the number of iterations and ''T ime ''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 ''I tb '', time ''Tb '') and with the minimum cost selection rule (iterations ''I tm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''I tl '', time ''Tl ''). 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''
|-
|||||''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
|}

{|
|+Table 160: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''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 ''Itb '', time ''Tb '') and with the minimum cost selection rule (iterations ''Itm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''Itl '', time ''Tl ''). 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''
|-
|||||''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
|}

{|
|+Table 161: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''is the number of iterations and ''T ime ''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 ''I tb '', time ''Tb '') and with the minimum cost selection rule (iterations ''I tm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''I tl '', time ''Tl ''). 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''
|-
|||||''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
|}

{|
|+Table 162: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''is the number of iterations and ''T ime ''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 ''I tb '', time ''Tb '') and with the minimum cost selection rule (iterations ''I tm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''I tl '', time ''Tl ''). 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''
|-
|||||''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
|}

{|
|+Table 163: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''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 ''I tb '', time ''Tb '') and with the minimum cost selection rule (iterations ''Itm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''I tl '', time ''Tl ''). 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''
|-
|||||''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
|}

{|
|+Table 164: Computational results on randomly generated medium size LP problems for four different routines. ''I ter ''is the number of iterations and ''T ime ''is the elapsed time in seconds on a Dell Latitude CPi266XT running Matlab 5.3. The ''lpS ''solver is the TOMLAB ''lpSimplex'', and it is run with both Bland's selection rule (iterations ''I tb '', time ''Tb '') and with the minimum cost selection rule (iterations ''I tm '', time T''m ''). The ''linprog ''solver in the Optimization Toolbox 2.0 implements two different algorithms, a medium-scale simplex algorithm (time ''Tm '') and a large-scale primal-dual interior-point method (iterations ''I tl '', time ''Tl ''). 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''
|-
|||||''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
|}

TOMLAB Appendix G - Revision history

Elias at 14:57, 14 January 2012

Elias at 11:55, 9 August 2011

Elias: moved Users Guide Appendix G to TOMLAB Appendix G

Elias: Created page with "=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'', tw..."