[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Complexity of your LP solver
|
From: |
Andrew Makhorin |
|
Subject: |
Re: [Help-glpk] Complexity of your LP solver |
|
Date: |
Sat, 7 Apr 2001 18:37:58 +0400 |
>In my search space I have to solve many small-scale (less than 100
>constraints) linear programming problems.
>Do you think GLPK would be a good tool for my need. Also, do you have
>any complexity analysis or benchmarks that can give me an idea how long
>it would take to solve each of these LP problems.
If your problems are pure LP (i.e. don't contain integer variables),
I'm sure that GLPK is able to efficiently solve such small problems.
As you probably know LP problems are not NP-complete, but the simplex
method has NP complexity, i.e. in the worst case it may require approx.
2**n iterations, where n is the problem dimension. However, practically
this never happens. I think that any LP problem with a hundred rows can
be solved by GLPK for few seconds or even less.
You can look at results of testing GLPK on a well known collection
of test LP problems from NETLIB <http://www.netlib.org/lp/data/> (see
below).
Best regards,
Andrew Makhorin
------------------------------------------------------------------------
Solver: GLPSOL 2.0 (options used: none)
Computer: Pentium II MMX 266 MHz
Platform: Debian GNU/Linux 2.2
Compiler: GCC 2.95.2 (options used: -O3)
Problem Rows Cols Nonzeros Optimum Iters Time,s Mem,MB
-------- ----- ----- -------- ------------ ----- ------ ------
25FV47 822 1571 11127 +5.50185E+03 2057 28.2 1.4
80BAU3B 2263 9799 29063 +9.87224E+05 4986 188.7 4.6
ADLITTLE 57 97 465 +2.25495E+05 83 0.1 0.1
AFIRO 28 32 88 -4.64753E+02 22 0.0 0.1
AGG 489 163 2541 -3.59918E+08 108 0.3 0.4
AGG2 517 302 4515 -2.02393E+07 194 0.7 0.6
AGG3 517 302 4531 -1.03121E+07 190 0.7 0.6
BANDM 306 472 2659 -1.58628E+02 483 1.6 0.4
BEACONFD 174 262 3476 +3.35925E+04 118 0.2 0.4
BLEND 75 83 521 -3.08121E+01 103 0.1 0.1
BNL1 644 1175 6129 +1.97763E+03 968 6.8 0.9
BNL2 2325 3489 16124 +1.81124E+03 2902 88.3 2.6
BOEING1 351 384 3865 -3.35214E+02 441 1.3 0.5
BOEING2 167 143 1339 -3.15019E+02 154 0.2 0.2
BORE3D 234 315 1525 +1.37308E+03 172 0.3 0.3
BRANDY 221 249 2150 +1.51851E+03 322 0.7 0.3
CAPRI 272 353 1786 +2.69001E+03 343 0.7 0.3
CYCLE 1904 2857 21322 -5.22639E+00 1235 29.1 2.7
CZPROB 930 3523 14173 +2.18520E+06 1437 19.1 2.0
D2Q06C 2172 5167 35674 +1.22784E+05 6666 386.9 4.2
D6CUBE 416 6184 43888 +3.15492E+02 7060 258.8 4.4
DEGEN2 445 534 4449 -1.43518E+03 1042 5.5 0.6
DEGEN3 1504 1818 26230 -9.87294E+02 3163 142.0 2.9
DFL001 6072 12230 41873 +1.12664E+07 33295 2 hrs 9.8 (a)
E226 224 282 2767 -1.87519E+01 276 0.7 0.3
ETAMACRO 401 688 2489 -7.55715E+02 536 1.8 0.5
FFFFF800 525 854 6235 +5.55680E+05 641 3.1 0.8
FINNIS 498 614 2714 +1.72791E+05 378 1.2 0.5
FIT1D 25 1026 14430 -9.14638E+03 571 3.5 1.2
FIT1P 628 1677 10894 +9.14638E+03 1140 13.9 1.4
FIT2D 26 10500 138018 -6.84643E+04 5736 585.8 11.6
FIT2P 3001 13525 60784 +6.84643E+04 11299 1309.9 8.1
FORPLAN 162 421 4916 -6.64219E+02 191 0.5 0.5
GANGES 1310 1681 7021 -1.09586E+05 1502 14.2 1.3
GFRD-PNC 617 1092 3467 +6.90224E+06 777 2.6 0.7
GREENBEA 2393 5405 31499 -7.25552E+07 7471 383.8 4.0
GREENBEB 2393 5405 31499 -4.30226E+06 5381 257.7 4.0
GROW15 301 645 5665 -1.06871E+08 919 5.5 0.7 (b)
GROW22 441 946 8318 -1.60834E+08 1680 16.8 1.1 (b)
GROW7 141 301 2633 -4.77878E+07 265 0.7 0.4
ISRAEL 175 142 2358 -8.96645E+05 130 0.3 0.3
KB2 44 41 291 -1.74990E+03 46 0.0 0.1
LOTFI 154 308 1086 -2.52647E+01 166 0.2 0.2
MAROS 847 1443 10006 -5.80637E+04 1350 13.9 1.3
MAROS-R7 3137 9408 151120 +1.49719E+06 4021 914.4 15.4
MODSZK1 688 1620 4158 +3.20620E+02 723 4.5 0.9
NESM 663 2923 13988 +1.40760E+07 3869 49.8 1.8
PEROLD 626 1376 6026 -9.38076E+03 1460 12.8 1.0
PILOT 1442 3652 43220 -5.57490E+02 9601 779.5 4.8 (b)
PILOT-JA 941 1988 14706 -6.11314E+03 2083 39.2 1.7
PILOT-WE 723 2789 9218 -2.72011E+06 1650 20.4 1.4
PILOT4 411 1000 5145 -2.58114E+03 932 5.7 0.8 (b)
PILOT87 2031 4883 73804 +3.01710E+02 6570 1146.7 8.5
PILOTNOV 976 2172 13129 -4.49728E+03 1341 21.2 1.7
RECIPE 92 180 752 -2.66616E+02 46 0.0 0.2
SC105 106 103 281 -5.22021E+01 94 0.1 0.1
SC205 206 203 552 -5.22021E+01 199 0.3 0.2
SC50A 51 48 131 -6.45751E+01 46 0.0 0.1
SC50B 51 48 119 -7.00000E+01 49 0.0 0.1
SCAGR25 472 500 2029 -1.47534E+07 633 2.4 0.5
SCAGR7 130 140 553 -2.33139E+06 143 0.1 0.2
SCFXM1 331 457 2612 +1.84168E+04 382 1.0 0.4
SCFXM2 661 914 5229 +3.66603E+04 757 4.3 0.8
SCFXM3 991 1371 7846 +5.49013E+04 1180 11.0 1.1
SCORPION 389 358 1708 +1.87812E+03 395 1.0 0.4
SCRS8 491 1169 4029 +9.04297E+02 660 2.9 0.7
SCSD1 78 760 3148 +8.66667E+00 101 0.2 0.4
SCSD6 148 1350 5666 +5.05000E+01 274 0.8 0.7
SCSD8 398 2750 11334 +9.05000E+02 886 7.1 1.5
SCTAP1 301 480 2052 +1.41225E+03 247 0.5 0.4
SCTAP2 1091 1880 8124 +1.72481E+03 1034 10.5 1.3
SCTAP3 1481 2480 10734 +1.42400E+03 1329 19.8 1.7
SEBA 516 1028 4874 +1.57116E+04 546 2.1 0.7
SHARE1B 118 225 1182 -7.65893E+04 198 0.2 0.2
SHARE2B 97 79 730 -4.15732E+02 98 0.1 0.1
SHELL 537 1775 4900 +1.20883E+09 747 3.4 0.9
SHIP04L 403 2118 8450 +1.79332E+06 466 2.3 1.2
SHIP04S 403 1458 5810 +1.79871E+06 420 1.5 0.8
SHIP08L 779 4283 17085 +1.90906E+06 743 9.7 2.3
SHIP08S 779 2387 9501 +1.92010E+06 634 4.8 1.4
SHIP12L 1152 5427 21597 +1.47019E+06 1313 25.6 2.9
SHIP12S 1152 2763 10941 +1.48924E+06 1073 11.8 1.7
SIERRA 1228 2036 9252 +1.53944E+07 916 9.7 1.4
STAIR 357 467 3857 -2.51267E+02 481 2.6 0.6
STANDATA 360 1075 3038 +1.25770E+03 70 0.2 0.6
STANDGUB 362 1184 3147 +1.25770E+03 70 0.2 0.6
STANDMPS 468 1075 3686 +1.40602E+03 321 1.1 0.6
STOCFOR1 118 111 474 -4.11320E+04 104 0.1 0.1
STOCFOR2 2158 2031 9492 -3.90244E+04 1896 38.9 1.8
STOCFOR3 16676 15695 74004 -3.99768E+04 15768 2 hrs 14.1
TRUSS 1001 8806 36642 +4.58816E+05 11934 481.6 4.6
TUFF 334 587 4523 +2.92148E-01 258 0.8 0.6
VTP-BASE 199 203 914 +1.29831E+05 184 0.3 0.2
WOOD1P 245 2594 70216 +1.44290E+00 451 17.2 5.4
WOODW 1099 8405 37478 +1.30448E+00 1511 51.1 4.6
(a) has been solved using --efi option; very slow convergence
solving using default --rfi-bg option was unsuccessful because of
numerical instability
(b) numerical instability