Comparisons are given for the cost values gotten by running the LP DASA
code to the cost values archived in the Netlib LP directory. The stopping
criterion for LP DASA, as discussed in the paper “A sparse proximal
implementation of the LP Dual Active Set Algorithm,” was based in the
relative error in the optimality conditions. The results given below
correspond to relative errors of 10^{-8} and 10^{-12}. The Netlib
objective function values appearing in column 4 below are the values
appearing at the top of the Netlib file, with the following exceptions:
The CPLEX values for some problems, given by Bob Bixby later in the file,
are used in place of the original values. Also, the values given for the
following problems, which appear to have 6 or 7 digit accuracy, are replaced
by more accurate values obtained using CPLEX: FINNIS, D2Q06C, and PILOT87.
Generally, the 10^{-8} criterion yields more than 8 significant digits
in the cost. Note though that for the 16 problems of Jeffrey Kennington,
only 8 digits are reported, so it is only possible to match these 8 digits.
As a group, the pilot problems (including PEROLD) and the 10^{-8} criterion
yield the poorest agreement with the archived cost. The agreement ranges
between 4 and 11 significant digits.
The worst agreement with the archived objective function values
occurs with GREENBEA for which there were only 3 significant digits with
the 10^{-8} stopping criterion. When the error tolerance was reduced
to 10^{-12}, the agreement increased to the 8th significant digit.
In fact, the LP DASA cost was better than the archived cost in the 8th digit:
LP DASA, GREENBEA, 10^{-12} tolerance, value = -7.25552503916e+07
The associated relative errors in the primal and dual residuals were
2.49e-13 and 5.97e-14.
The second worst agreement with the archived objected function values occurs
with FFFFF800 for which there were only 4 significant digits with the 10^{-8}
stopping criterion. When the error tolerance was reduced to 10^{-12}, the
agreement increased to the 11 digits listed in the Netlib archive.
Digits is given by the formula: floor (.5 – log10 (abs(netlib – lpdasa)/abs (netlib)))
===========================================================================================================================
Netlib LP DASA LP DASA Relative Relative
Name Rows Cols Nonzeros Optimal Value Optimal Value Digits Optimal Value b-err c-err Digits
10^(-8) Tol 10^(-12) Tol
25FV47 822 1571 11127 5.5018458883E+03 5.5018458836e+03 (09) 5.50184588829e+03 1.01e-14 2.87e-18 (12)
80BAU3B 2263 9799 29063 9.8722419241E+05 9.8722418531e+05 (08) 9.87224192409e+05 2.84e-16 3.67e-18 (12)
ADLITTLE 57 97 465 2.2549496316E+05 2.2549496302e+05 (09) 2.25494963163e+05 8.90e-14 1.02e-17 (11)
AFIRO 28 32 88 -4.6475314286E+02 -4.6475314286e+02 (11) -4.64753142857e+02 3.59e-14 2.95e-17 (11)
AGG 489 163 2541 -3.5991767287E+07 -3.5991769285e+07 (07) -3.59917672878e+07 1.27e-14 7.98e-19 (11)
AGG2 517 302 4515 -2.0239252356E+07 -2.0239252356e+07 (11) -2.02392523560e+07 1.94e-19 3.31e-20 (12)
AGG3 517 302 4531 1.0312115935E+07 1.0312115935e+07 (12) 1.03121159351e+07 1.04e-18 2.26e-19 (11)
BANDM 306 472 2659 -1.5862801845E+02 -1.5862801847e+02 (10) -1.58628018450e+02 3.79e-20 1.53e-16 (12)
BEACONFD 174 262 3476 3.3592485807E+04 3.3592485817e+04 (10) 3.35924858072e+04 9.01e-22 2.59e-18 (11)
BLEND 75 83 521 -3.0812149846E+01 -3.0812149846e+01 (11) -3.08121498458e+01 7.11e-22 3.06e-16 (11)
BNL1 644 1175 6129 1.9776295615E+03 1.9776295615e+03 (11) 1.97762956152e+03 4.65e-13 2.03e-18 (11)
BNL2 2325 3489 16124 1.8112365404E+03 1.8112367470e+03 (07) 1.81123654036e+03 4.50e-15 4.01e-18 (11)
BORE3D 234 315 1525 1.3730803942E+03 1.3730803942e+03 (11) 1.37308039421e+03 2.04e-16 1.52e-19 (11)
BRANDY 221 249 2150 1.5185098965E+03 1.5185098965e+03 (11) 1.51850989649e+03 2.61e-20 1.23e-20 (11)
CAPRI 272 353 1786 2.6900129138E+03 2.6900131064e+03 (07) 2.69001291377e+03 9.18e-16 5.37e-19 (11)
CRE-A 3517 4067 19054 2.3595407e+07 2.3595407434e+07 (08) 2.35954070610e+07 1.02e-15 3.61e-20 (09)
CRE-B 9649 72447 328542 2.3129640e+07 2.3129639887e+07 (08) 2.31296398868e+07 5.21e-13 3.24e-18 (08)
CRE-C 3069 3678 16922 2.5275116e+07 2.5275116153e+07 (08) 2.52751161409e+07 4.52e-13 1.16e-18 (08)
CRE-D 8927 69980 312626 2.4454970e+07 2.4454969890e+07 (08) 2.44549697645e+07 4.32e-13 3.70e-19 (08)
CYCLE 1904 2857 21322 -5.2263930249E+00 -5.2263930249e+00 (12) -5.22639302489e+00 3.54e-13 2.54e-17 (12)
CZPROB 930 3523 14173 2.1851966989E+06 2.1851966987e+06 (10) 2.18519669886e+06 2.41e-14 5.47e-15 (11)
D2Q06C 2172 5167 35674 1.2278421081e+05 1.2278421081e+05 (10) 1.22784210814e+05 3.61e-16 3.30e-17 (10)
D6CUBE 416 6184 43888 3.1549166667E+02 3.1549166667e+02 (11) 3.15491666667e+02 4.84e-14 4.02e-16 (11)
DEGEN2 445 534 4449 -1.4351780000E+03 -1.4351779999e+03 (10) -1.43517800000e+03 1.17e-16 5.14e-18 (16)
DEGEN3 1504 1818 26230 -9.8729400000E+02 -9.8729399999e+02 (11) -9.87294000000e+02 3.63e-17 5.03e-15 (16)
DFL001 6072 12230 41873 1.1266396047E+07 1.1266566641e+07 (05) 1.12663960467e+07 1.77e-16 1.84e-18 (11)
E226 224 282 2767 -1.8751929066E+01 -1.8751929067e+01 (10) -1.87519290664e+01 2.26e-14 1.77e-17 (11)
ETAMACRO 401 688 2489 -7.5571523337E+02 -7.5571523112e+02 (09) -7.55715233357e+02 1.75e-19 7.81e-13 (11)
FFFFF800 525 854 6235 5.5567956482E+05 5.5571575854e+05 (04) 5.55679564817e+05 2.81e-13 7.01e-18 (11)
FINNIS 498 614 2714 1.7279106560e+05 1.7279106512e+05 (09) 1.72791065596e+05 2.85e-13 2.14e-19 (11)
FIT1D 25 1026 14430 -9.1463780924E+03 -9.1463780909e+03 (10) -9.14637809242e+03 1.82e-20 1.51e-15 (12)
FIT1P 628 1677 10894 9.1463780924E+03 9.1463780924e+03 (12) 9.14637809242e+03 1.49e-21 2.32e-15 (12)
FIT2D 26 10500 138018 -6.8464293294E+04 -6.8464293294e+04 (12) -6.84642932938e+04 3.45e-21 3.58e-16 (12)
FIT2P 3001 13525 60784 6.8464293232E+04 6.8464293294e+04 (09) 6.84642932938e+04 1.02e-19 2.53e-14 (09)
GANGES 1310 1681 7021 -1.0958573613E+05 -1.0958573613e+05 (11) -1.09585736129e+05 8.25e-15 1.57e-15 (11)
GFRD-PNC 617 1092 3467 6.9022359995E+06 6.9022359731e+06 (08) 6.90223599955e+06 4.12e-19 2.58e-15 (11)
GREENBEA 2393 5405 31499 -7.2555248130E+07 -7.2462440347e+07 (03) -7.25552503916e+07 2.49e-13 5.97e-14 (08)
GREENBEB 2393 5405 31499 -4.3022602612E+06 -4.3022602608e+06 (10) -4.30226026121e+06 3.15e-13 3.12e-18 (12)
GROW15 301 645 5665 -1.0687094129E+08 -1.0687094129e+08 (10) -1.06870941294e+08 9.68e-14 2.85e-17 (10)
GROW22 441 946 8318 -1.6083433648E+08 -1.6083433648e+08 (11) -1.60834336483e+08 5.62e-14 1.58e-17 (11)
GROW7 141 301 2633 -4.7787811815E+07 -4.7787811815e+07 (11) -4.77878118147e+07 4.25e-14 1.94e-17 (11)
ISRAEL 175 142 2358 -8.9664482186E+05 -8.9664482186e+05 (11) -8.96644821863e+05 1.10e-14 9.58e-19 (11)
KB2 44 41 291 -1.7499001299E+03 -1.7499001299e+03 (11) -1.74990012991e+03 4.21e-17 1.24e-13 (11)
KEN-07 2427 3602 11981 -6.7952044e+08 -6.7952044339e+08 (08) -6.79520443382e+08 3.45e-18 1.97e-15 (08)
KEN-11 14695 21349 70354 -6.9723823e+09 -6.9723822625e+09 (08) -6.97238226252e+09 6.84e-18 2.02e-17 (08)
KEN-13 28633 42659 139834 -1.0257395e+10 -1.0257394789e+10 (08) -1.02573947895e+10 1.78e-16 9.76e-18 (08)
KEN-18 105128 154699 512719 -5.2217025e+10 -5.2217025287e+10 (08) -5.22170252874e+10 5.68e-17 5.22e-15 (08)
LOTFI 154 308 1086 -2.5264706062E+01 -2.5264706062e+01 (11) -2.52647060615e+01 7.36e-15 1.95e-18 (11)
MAROS 847 1443 10006 -5.8063743701E+04 -5.8063743701e+04 (12) -5.80637437011e+04 1.12e-13 1.52e-20 (12)
MAROS-R7 3137 9408 151120 1.4971851665E+06 1.4971851665e+06 (11) 1.49718516648e+06 3.25e-22 9.07e-17 (11)
MODSZK1 688 1620 4158 3.2061972906E+02 3.2061972909e+02 (10) 3.20619729090e+02 3.54e-17 8.33e-15 (10)
OSA-07 1119 23949 167643 5.3572252e+05 5.3572251730e+05 (08) 5.35722517299e+05 1.39e-17 3.90e-18 (08)
OSA-14 2338 52460 367220 1.1064628e+06 1.1064628449e+06 (07) 1.10646284474e+06 3.47e-17 4.99e-18 (07)
OSA-30 4351 100024 700160 2.1421399e+06 2.1421398738e+06 (08) 2.14213987321e+06 5.84e-18 5.44e-18 (08)
OSA-60 10281 232966 1630758 4.0440725e+06 4.0440725055e+06 (09) 4.04407250316e+06 3.47e-17 7.32e-18 (09)
PDS-02 2954 7535 21252 2.8857862e+10 2.8857862010e+10 (09) 2.88578620100e+10 1.40e-15 9.05e-19 (09)
PDS-06 9882 28655 82269 2.7761038e+10 2.7761037600e+10 (08) 2.77610376000e+10 1.39e-13 1.85e-16 (08)
PDS-10 16559 48763 140063 2.6727095e+10 2.6727094976e+10 (09) 2.67270949760e+10 2.51e-15 8.07e-14 (09)
PDS-20 33875 105728 304153 2.3821659e+10 2.3821658640e+10 (08) 2.38216586400e+10 6.15e-14 4.63e-15 (08)
PEROLD 626 1376 6026 -9.3807552782E+03 -9.3807578160e+03 (07) -9.38075527829e+03 4.09e-15 5.80e-19 (11)
PILOT 1442 3652 43220 -5.5748972928E+02 -5.5747482669e+02 (05) -5.57489729284e+02 1.37e-18 1.45e-17 (11)
PILOT.JA 941 1988 14706 -6.1131364656E+03 -6.1131345861e+03 (07) -6.11313646558e+03 8.50e-15 6.12e-13 (12)
PILOT.WE 723 2789 9218 -2.7201075328E+06 -2.7199466997e+06 (04) -2.72010753286e+06 2.86e-16 6.21e-13 (11)
PILOT4 411 1000 5145 -2.5811392589E+03 -2.5811375521e+03 (06) -2.58113925888e+03 1.15e-21 1.38e-13 (11)
PILOT87 2031 4883 73804 3.0171034733E+02 3.0171062422e+02 (06) 3.01710347333e+02 2.01e-15 7.59e-14 (11)
PILOTNOV 976 2172 13129 -4.4972761882E+03 -4.4972761882e+03 (11) -4.49727618822e+03 4.56e-15 4.52e-15 (11)
QAP8 913 1632 8304 2.0350000000E+02 2.0350000000e+02 (15) 2.03500000000e+02 4.51e-14 8.00e-17 (14)
QAP12 3193 8856 44244 5.2289435056E+02 5.2289435056e+02 (12) 5.22894350559e+02 1.58e-13 3.30e-18 (12)
QAP15 6331 22275 110700 1.0409940410E+03 1.0409940410e+03 (10) 1.04099404096e+03 4.62e-13 4.66e-18 (10)
RECIPE 92 180 752 -2.6661600000E+02 -2.6661600000e+02 (11) -2.66616000000e+02 6.94e-18 2.50e-17 (15)
SC105 106 103 281 -5.2202061212E+01 -5.2202060187e+01 (08) -5.22020612117e+01 2.82e-20 2.95e-15 (11)
SC205 206 203 552 -5.2202061212E+01 -5.2202061212e+01 (11) -5.22020612117e+01 1.15e-14 3.36e-15 (11)
SC50A 51 48 131 -6.4575077059E+01 -6.4575077038e+01 (09) -6.45750770586e+01 3.20e-17 7.87e-16 (11)
SC50B 51 48 119 -7.0000000000E+01 -6.9999999978e+01 (09) -7.00000000000e+01 1.04e-22 3.78e-15 (16)
SCAGR25 472 500 2029 -1.4753433061E+07 -1.4753433082e+07 (09) -1.47534330608e+07 6.32e-20 1.79e-16 (11)
SCAGR7 130 140 553 -2.3313898243E+06 -2.3313898234e+06 (09) -2.33138982433e+06 7.23e-20 1.40e-17 (11)
SCFXM1 331 457 2612 1.8416759028E+04 1.8416759028e+04 (11) 1.84167590283e+04 6.36e-14 3.26e-17 (11)
SCFXM2 661 914 5229 3.6660261565E+04 3.6660261565e+04 (12) 3.66602615650e+04 7.37e-15 8.60e-18 (13)
SCFXM3 991 1371 7846 5.4901254550E+04 5.4901254550e+04 (11) 5.49012545498e+04 6.96e-15 8.60e-18 (11)
SCORPION 389 358 1708 1.8781248227E+03 1.8781248227e+03 (11) 1.87812482274e+03 6.73e-18 2.72e-19 (11)
SCRS8 491 1169 4029 9.0429695380E+02 9.0429695380e+02 (12) 9.04296953801e+02 8.34e-17 2.75e-22 (12)
SCSD1 78 760 3148 8.6666666743E+00 8.6666666743e+00 (11) 8.66666667433e+00 5.73e-14 1.77e-15 (11)
SCSD6 148 1350 5666 5.0500000077E+01 5.0500000078e+01 (11) 5.05000000771e+01 7.28e-16 4.63e-18 (12)
SCSD8 398 2750 11334 9.0499999993E+02 9.0500000097e+02 (09) 9.04999999925e+02 2.14e-14 2.30e-13 (11)
SCTAP1 301 480 2052 1.4122500000E+03 1.4122500000e+03 (15) 1.41225000000e+03 1.74e-14 2.34e-18 (14)
SCTAP2 1091 1880 8124 1.7248071429E+03 1.7248071429e+03 (11) 1.72480714286e+03 8.94e-14 9.28e-18 (11)
SCTAP3 1481 2480 10734 1.4240000000E+03 1.4240000000e+03 (14) 1.42400000000e+03 3.84e-14 1.58e-17 (14)
SHARE1B 118 225 1182 -7.6589318579E+04 -7.6589318579e+04 (12) -7.65893185792e+04 4.74e-19 3.86e-16 (12)
SHARE2B 97 79 730 -4.1573224074E+02 -4.1573223926e+02 (08) -4.15732240741e+02 3.22e-17 3.63e-15 (11)
SHELL 537 1775 4900 1.2088253460E+09 1.2088253460e+09 (11) 1.20882534600e+09 6.37e-17 2.10e-16 (16)
SHIP04L 403 2118 8450 1.7933245380E+06 1.7933245379e+06 (10) 1.79332453797e+06 5.66e-23 8.05e-17 (11)
SHIP04S 403 1458 5810 1.7987147004E+06 1.7987147001e+06 (10) 1.79871470045e+06 9.16e-21 1.32e-15 (11)
SHIP08L 779 4283 17085 1.9090552114E+06 1.9090552115e+06 (10) 1.90905521139e+06 4.13e-21 1.66e-15 (11)
SHIP08S 779 2387 9501 1.9200982105E+06 1.9200982105e+06 (11) 1.92009821053e+06 1.21e-22 6.77e-17 (11)
SHIP12L 1152 5427 21597 1.4701879193E+06 1.4701879194e+06 (10) 1.47018791933e+06 3.71e-18 1.33e-16 (11)
SHIP12S 1152 2763 10941 1.4892361344E+06 1.4892361344e+06 (11) 1.48923613441e+06 1.97e-16 5.32e-16 (11)
SIERRA 1228 2036 9252 1.5394362184E+07 1.5394362206e+07 (09) 1.53943621836e+07 6.32e-17 1.73e-18 (11)
STAIR 357 467 3857 -2.5126695119E+02 -2.5126695389e+02 (08) -2.51266951193e+02 1.25e-22 4.14e-20 (11)
STANDATA 360 1075 3038 1.2576995000E+03 1.2576995000e+03 (11) 1.25769950000e+03 3.86e-15 2.57e-15 (16)
STANDMPS 468 1075 3686 1.4060175000E+03 1.4060175000e+03 (16) 1.40601750000e+03 1.51e-13 7.36e-15 (12)
STOCFOR1 118 111 474 -4.1131976219E+04 -4.1131976734e+04 (08) -4.11319762194e+04 1.93e-18 6.52e-15 (11)
STOCFOR2 2158 2031 9492 -3.9024408538E+04 -3.9024408608e+04 (09) -3.90244085379e+04 1.37e-17 4.36e-15 (12)
STOCFOR3 16676 15695 74004 -3.9976783944E+04 -3.9976783941e+04 (10) -3.99767839436e+04 3.37e-17 5.79e-21 (11)
TRUSS 1001 8806 36642 4.5881584719E+05 4.5881584719e+05 (11) 4.58815847186e+05 3.71e-17 2.13e-18 (11)
TUFF 334 587 4523 2.9214776509E-01 2.9214776505e-01 (10) 2.92147765094e-01 1.52e-14 8.41e-15 (11)
VTP.BASE 199 203 914 1.2983146246E+05 1.2983146243e+05 (10) 1.29831462461e+05 3.01e-19 6.95e-18 (11)
WOOD1P 245 2594 70216 1.4429024116E+00 1.4429024184e+00 (08) 1.44290241157e+00 1.42e-13 3.96e-17 (11)
WOODW 1099 8405 37478 1.3044763331E+00 1.3044763350e+00 (09) 1.30447633308e+00 2.07e-13 6.95e-15 (11)