Several people demanded to know about the performance of ALGENCAN in linear programming problems. Needless to say, ALGENCAN is not a method designed for linear programming, a problem in which specific characteristics make it recommendable to use specific algorithms. For example, as it is well known, the Simplex method updates matrix factorizations at a low cost, whenever a linear system needs to be solved. Nevertheless, since Linear Programming is a particular case of Nonlinear Programming, to register the performance of nonlinear programming solvers in LP problems may be quite interesting. We describe the application of ALGENCAN to the 98 linear programming problems from Netlib. We consider the SIF description of the problems available at: http://www.numerical.rl.ac.uk/cuter-www/Problems/netlib.shtml A detailed analysis of the Netlib LP problems, and the application of other solvers to them, can be found in: http://www.netlib.org/lp/data/readme Our experiments were run on a 2.4GHz Intel Core2 Quad Q6600 with 4.0GB of RAM memory and Linux Operating System. When the objective function given to ALGENCAN is quadratic (or linear) and one only has linear equality constraints and bounds, the Augmented Lagrangian subproblems are box-constraint smooth quadratic problems. This is a good reason to reformulate linear inequality constraints using slack variables and additional bounds. Note that, when the number of inequality constraints is enormous, the advantage of this reformulation may be lost. In the case of Netlib problems we decided for the slack reformulation. Therefore, we used the non-default option: ADD-SLACKS This is not a default choice because there is no way to let ALGENCAN know that the objective function is linear or quadratic. Other than that, all the default ALGENCAN parameters were used in the first round of these experiments. In particular, the default stopping criterion associated with convergence requires optimality, feasibility and complementarity measurements to be less than or equal to 1.0d-08. Note that this is particularly a very questionable option, because it is radically affected by scaling. Clever users should scale their problems in such a way that this stopping criterion means something for them, or, alternatively, they should change the stopping criterion. The current version of ALGENCAN (version 2.3.2) successfully solved all the 98 linear programming problems from Netlib in February 2010. The way in which these problems were solved is reported below. a) In its first run ALGENCAN satisfied its stopping criterion associated with convergence in 91 problems. In other 6 problems (DFL001, FIT2D, GREENBEA, NESM, PILOT4, PILOT-WE) ALGENCAN found the solution up to any reasonable human criterion but, due to scaling issues, failed to satisfy the stopping criterion associated with convergence. In only one problem (PILOT-JA) ALGENCAN failed to find a feasible point. The following table reports the results of this first run. Observe that we give the value of the objective function found, as well as the value provided in the Netlib site. We also report the sup-norm of (unscaled) constraint violations. Recall that box-constraints are never violated in ALGENCAN, therefore constraint violations refer only to equality (linear) constraints in this case. In the table, the columns mean: n : number of variables m : number of constraints f : (unscaled) objective value found at the final iterate ||c|| : sup-norm of the (unscaled) constraints ||g|| : sup-norm of the scaled projected gradient of the Lagrangian SC : Stopping criteria (0 means solution was found, 1 means too large penalty parameter, 2 means maximum number of iterations reached) Time : CPU time in seconds Reported f : Optimal Value reported at http://www.netlib.org/lp/data/readme --------------------------------------------------------------------------------------- Problem n m f ||c|| ||g|| SC Time Reported f --------------------------------------------------------------------------------------- 25FV47 1571 821 5.5018458848829196D+03 9.2D-13 9.4D-09 0 20.27 5.5018458883E+03 80BAU3B 9799 2262 9.8722419240897824D+05 1.2D-09 8.5D-09 0 36.79 9.8723216072E+05 ADLITTLE 97 56 2.2549496316243065D+05 2.6D-10 1.9D-10 0 0.07 2.2549496316E+05 AFIRO 32 27 -4.6475314285714290D+02 1.7D-13 5.4D-14 0 0.01 -4.6475314286E+02 AGG 163 488 -3.5991767286575869D+07 9.3D-10 9.3D-10 0 4.12 -3.5991767287E+07 AGG2 302 516 -2.0239252355977114D+07 1.1D-10 6.9D-10 0 1.19 -2.0239252356E+07 AGG3 302 516 1.0312115935089229D+07 3.1D-10 1.7D-11 0 1.42 1.0312115935E+07 BANDM 472 305 -1.5862801845012063D+02 1.6D-13 3.1D-15 0 1.62 -1.5862801845E+02 BEACONFD 262 173 3.3592485807200021D+04 2.0D-10 6.8D-14 0 0.69 3.3592485807E+04 BLEND 83 74 -3.0812149845828223D+01 1.9D-14 1.4D-09 0 0.05 -3.0812149846E+01 BNL1 1175 643 1.9776295615228892D+03 3.0D-13 5.4D-09 0 41.55 1.9776292856E+03 BNL2 3489 2324 1.8112365403585477D+03 2.3D-13 3.5D-09 0 165.64 1.8112365404E+03 BOEING1 384 440 -3.3521356750712675D+02 7.3D-12 9.9D-09 0 26.81 -3.3521356751E+02 BOEING2 143 185 -3.1501872801520261D+02 1.5D-11 8.0D-09 0 1.70 -3.1501872802E+02 BORE3D 315 233 1.3730803942084926D+03 2.3D-13 9.8D-09 0 0.39 1.3730803942E+03 BRANDY 249 220 1.5185098964879571D+03 3.9D-10 1.8D-09 0 1.21 1.5185098965E+03 CAPRI 353 271 2.6900129137683393D+03 2.0D-12 3.2D-09 0 1.77 2.6900129138E+03 CYCLE 2857 1903 -5.2263930248941026D+00 9.1D-12 9.7D-09 0 183.64 -5.2263930249E+00 CZPROB 3523 929 2.1851966988565754D+06 1.1D-12 3.9D-14 0 10.85 2.1851966989E+06 D2Q06C 5167 2171 1.2278421072139232D+05 3.4D-11 7.1D-09 0 154.76 1.2278423615E+05 D6CUBE 6184 415 3.1549166666666679D+02 7.5D-13 9.1D-11 0 11.29 3.1549166667E+02 DEGEN2 534 444 -1.4351779999999997D+03 3.6D-15 3.9D-10 0 1.01 -1.4351780000E+03 DEGEN3 1818 1503 -9.8729400000000101D+02 1.1D-14 1.1D-09 0 24.70 -9.8729400000E+02 DFL001 12230 6071 1.1266449695762150D+07 6.8D-10 2.4D-04 2 9692.94 1.12664E+07 ** E226 282 223 -1.1638929066370540D+01 2.1D-14 5.0D-12 0 2.85 -1.8751929066E+01 ETAMACRO 688 400 -7.5571523165886913D+02 1.8D-11 4.6D-09 0 2.40 -7.5571521774E+02 FFFFF800 854 524 5.5567956481749658D+05 7.0D-11 8.9D-09 0 11.11 5.5567961165E+05 FINNIS 614 497 1.7279106568633881D+05 3.4D-12 2.3D-09 0 0.86 1.7279096547E+05 FIT1D 1026 24 -9.1463780924210023D+03 1.8D-12 1.2D-12 0 1.44 -9.1463780924E+03 FIT1P 1677 627 9.1463780924209204D+03 8.5D-14 2.2D-11 0 1.32 9.1463780924E+03 FIT2D 10500 25 -6.8412660410241297D+04 8.6D-11 4.0D+01 2 409.76 -6.8464293294E+04 FIT2P 13525 3000 6.8464293293832117D+04 8.5D-14 2.3D-10 0 20.07 6.8464293232E+04 FORPLAN 421 162 -6.6421896127220441D+02 1.7D-12 8.0D-11 0 5.59 -6.6421873953E+02 GANGES 1681 1309 -1.0958573612927795D+05 1.5D-11 2.3D-12 0 12.96 -1.0958636356E+05 GFRD-PNC 1092 616 6.9022359995488189D+06 3.6D-12 4.9D-09 0 3.59 6.9022359995E+06 GREENBEA 5405 2392 -7.2543865837989122D+07 2.0D-08 1.3D+12 1 637.00 -7.2462405908E+07 GREENBEB 5405 2392 -4.3022602612065831D+06 4.0D-12 9.0D-09 0 602.43 -4.3021476065E+06 GROW15 645 300 -1.0687094129357535D+08 2.6D-10 5.9D-12 0 2.49 -1.0687094129E+08 GROW22 946 440 -1.6083433648256302D+08 2.2D-10 1.5D-11 0 3.55 -1.6083433648E+08 GROW7 301 140 -4.7787811814711504D+07 1.0D-10 3.0D-14 0 0.54 -4.7787811815E+07 ISRAEL 142 174 -8.9664482186304615D+05 2.4D-11 3.0D-11 0 0.75 -8.9664482186E+05 KB2 41 43 -1.7499001299062056D+03 1.8D-12 4.4D-12 0 0.04 -1.7499001299E+03 LOTFI 308 153 -2.5264706061879991D+01 1.9D-09 8.3D-15 0 0.87 -2.5264706062E+01 MAROS 1443 846 -5.8063743701125903D+04 5.5D-10 3.3D-09 0 59.99 -5.8063743701E+04 MAROS-R7 9408 3136 1.4971851664796444D+06 1.8D-11 2.5D-14 0 18.15 1.4971851665E+06 MODSZK1 1620 687 3.2061972906415230D+02 5.8D-11 1.7D-10 0 1.31 3.2061972906E+02 NESM 2923 750 1.4076038511311354D+07 6.1D-10 7.3D+00 2 392.63 1.4076073035E+07 PEROLD 1376 625 -9.3807552793602499D+03 2.3D-10 9.0D-09 0 69.08 -9.3807580773E+03 PILOT 3652 1441 -5.6849814021593397D+02 3.2D-12 5.1D-09 0 504.92 -5.5740430007E+02 PILOT-JA 1988 940 -6.1155707801332837D+03 3.3D+02 8.9D+11 1 735.01 -6.1131344111E+03 PILOT-WE 2789 722 -2.7198489284369885D+06 1.8D-09 1.4D+00 2 380.83 -2.7201027439E+06 PILOT4 1000 410 -2.5809908451756032D+03 1.7D-08 7.7D+05 2 66.55 -2.5811392641E+03 PILOT87 4883 2030 3.0116416829443818D+02 6.0D-12 3.8D-13 0 4735.96 3.0171072827E+02 PILOTNOV 2172 975 -4.4972761851355281D+03 1.2D-10 7.9D-09 0 45.92 -4.4972761882E+03 QAP8 1632 912 2.0350000000000006D+02 1.6D-15 1.3D-09 0 6.21 2.0350000000E+02 QAP12 8856 3192 5.2289435055906802D+02 2.8D-16 5.4D-09 0 862.08 5.2289435056E+02 QAP15 22275 6330 1.0409940409540384D+03 4.3D-11 9.8D-09 0 368.38 1.0409940410E+03 RECIPELP 180 91 -2.6661599999999999D+02 3.6D-15 5.1D-15 0 0.02 -2.6661600000E+02 SC105 103 105 -5.2202061211734353D+01 3.2D-11 5.6D-11 0 0.07 -5.2202061212E+01 SC205 203 205 -5.2202061211953684D+01 3.0D-10 4.6D-09 0 0.44 -5.2202061212E+01 SC50A 48 50 -6.4575077058563835D+01 4.4D-12 3.6D-10 0 0.01 -6.4575077059E+01 SC50B 48 50 -6.9999999999999105D+01 5.7D-14 8.2D-12 0 0.02 -7.0000000000E+01 SCAGR25 500 471 -1.4753433060769398D+07 1.5D-11 5.3D-13 0 2.70 -1.4753433061E+07 SCAGR7 140 129 -2.3313898243309846D+06 6.8D-13 5.2D-13 0 0.25 -2.3313892548E+06 SCFXM1 457 330 1.8416759028348948D+04 3.6D-12 1.0D-08 0 2.82 1.8416759028E+04 SCFXM2 914 660 3.6660261564998815D+04 3.1D-12 1.9D-09 0 3.23 3.6660261565E+04 SCFXM3 1371 990 5.4901254549751451D+04 2.1D-12 6.8D-10 0 6.00 5.4901254550E+04 SCORPION 358 388 1.8781248227381075D+03 1.7D-16 2.9D-09 0 0.24 1.8781248227E+03 SCRS8 1169 490 9.0429695380079181D+02 2.8D-14 8.1D-09 0 6.60 9.0429998619E+02 SCSD1 760 77 8.6666666897020441D+00 6.6D-09 7.3D-09 0 0.14 8.6666666743E+00 SCSD6 1350 147 5.0500000076437523D+01 9.0D-11 9.9D-09 0 0.45 5.0500000078E+01 SCSD8 2750 397 9.0499999992546475D+02 3.6D-15 1.0D-09 0 5.31 9.0499999993E+02 SCTAP1 480 300 1.4122500000000005D+03 1.1D-14 1.0D-09 0 0.83 1.4122500000E+03 SCTAP2 1880 1090 1.7248071428571432D+03 1.4D-13 6.2D-11 0 1.54 1.7248071429E+03 SCTAP3 2480 1480 1.4240000000000005D+03 7.1D-15 4.6D-09 0 3.03 1.4240000000E+03 SEBA 1028 522 1.5711600000003793D+04 6.4D-12 3.3D-09 0 0.27 1.5711600000E+04 SHARE1B 225 117 -7.6589318579185609D+04 1.2D-10 7.3D-13 0 1.58 -7.6589318579E+04 SHARE2B 79 96 -4.1573224074140109D+02 5.4D-13 3.8D-09 0 0.14 -4.1573224074E+02 SHELL 1775 536 1.2088253460000000D+09 1.1D-11 4.3D-10 0 0.72 1.2088253460E+09 SHIP04L 2118 402 1.7933245379703564D+06 9.7D-15 4.2D-10 0 0.99 1.7933245380E+06 SHIP04S 1458 402 1.7987147004453917D+06 1.2D-14 9.1D-13 0 0.63 1.7987147004E+06 SHIP08L 4283 778 1.9090552113891314D+06 9.4D-15 4.0D-09 0 5.05 1.9090552114E+06 SHIP08S 2387 778 1.9200982108214612D+06 1.5D-09 1.1D-09 0 1.92 1.9200982105E+06 SHIP12L 5427 1151 1.4701879193292661D+06 4.8D-14 5.4D-09 0 7.79 1.4701879193E+06 SHIP12S 2763 1151 1.4892361344061326D+06 2.2D-13 1.7D-11 0 5.63 1.4892361344E+06 SIERRA 2036 1227 1.5394362183631931D+07 1.5D-11 4.4D-09 0 3.09 1.5394362184E+07 STAIR 467 356 -2.5126695119296329D+02 5.7D-14 4.1D-14 0 1.23 -2.5126695119E+02 STANDATA 1075 359 1.2576994999999999D+03 2.3D-13 1.8D-15 0 0.06 1.2576995000E+03 STANDGUB 1184 361 1.2576994999999999D+03 7.1D-15 3.0D-14 0 0.07 (see NOTES) STANDMPS 1075 467 1.4060174999999999D+03 1.1D-13 4.5D-09 0 0.22 1.4060175000E+03 STOCFOR1 111 117 -4.1131976219436416D+04 1.2D-12 1.4D-14 0 0.16 -4.1131976219E+04 STOCFOR2 2031 2157 -3.9024408537882045D+04 1.3D-12 3.8D-09 0 15.77 -3.9024408538E+04 STOCFOR3 15695 16675 -3.9976783940713452D+04 1.6D-12 9.4D-09 0 768.31 -3.9976661576E+04 TRUSS 8806 1000 4.5881584718561644D+05 1.1D-13 1.7D-09 0 83.66 4.5881584719E+05 TUFF 587 333 2.9214776509361279D-01 7.4D-13 5.9D-09 0 0.55 2.9214776509E-01 VTP-BASE 203 198 1.2983146246136139D+05 4.5D-11 4.9D-09 0 8.72 1.2983146246E+05 WOOD1P 2594 244 1.4429024115734082D+00 3.3D-14 4.2D-10 0 3.29 1.4429024116E+00 WOODW 8405 1098 1.3044763330842295D+00 7.1D-14 2.2D-09 0 10.12 1.3044763331E+00 From now on we restrict our report to the 7 problems that were not solved with the required criterion in the first round (stopping criterion different from 0). b) In a second round, we run ALGENCAN increasing the penalty parameter more slowly (we changed rhomult from 1.0d+01 to 1.1d+00) and, in consequence, allowing a larger number of outer iterations (we changed maxoutit from 50 to 1000). We run only those 7 problems for which the stopping criterion associated with convergence was not satisfied in the first round. The results are given in the table below. We observe that in four cases (DFL001, FIT2D, NESM, PILOT4) the default convergence stopping criterion was satisfied. Three problems remained in which the default convergence criterion was not satisfied: GREENBEA, PILOT-JA and PILOT-WE. The maximum number of iterations (maxoutit = 1000) was exhausted in PILOT-WE, whereas the penalty parameter exceeded the value 1.0d+20 (rhomax) in GREENBEA and PILOT-JA. In GREENBEA it was not possible to achieve feasibility with precision smaller than 1.0d-08. (We obtained 2.1d-08.) In this case, the penalty parameter was increased more and more, without getting that precision, until the maximum value rhomax = 1.0d+20 was achieved. Moreover, the very large penalty parameter inhibited the possibility of reducing the projected gradient of the augmented Lagrangian in the subproblems solver GENCAN. Observe, however that the objective function value is slightly lower (difference in the 3rd digit) than the one reported by Netlib. In PILOT-JA the maximum allowed value for the penalty parameter was also achieved trying to obtain infeasibility smaller than 1.0d-08. (We got 7.5d-07.) In this case, the objective function value was slightly higher than the reported one (difference in the 6th digit). In PILOT-WE we obtained a feasible (1.0d-08) point, but the norm of the projected gradient of the Lagrangian remained greater than 1.0d-05. In this case the number of iterations was exhausted. Note, however, the the objective function value obtained by ALGENCAN was slightly lower (difference in the 7th digit) than the one reported by Netlib. --------------------------------------------------------------------------------------- Problem n m f ||c|| ||g|| SC Time Reported f --------------------------------------------------------------------------------------- DFL001 12230 6071 1.1266396047118297D+07 2.4D-09 9.7D-09 0 1347.46 1.12664E+07 ** FIT2D 10500 25 -6.8464293293832103D+04 1.0D-11 1.4D-13 0 251.30 -6.8464293294E+04 GREENBEA 5405 2392 -7.2555248124438524D+07 2.1D-08 5.3D+11 1 2519.07 -7.2462405908E+07 NESM 2923 750 1.4076036487565519D+07 1.0D-08 2.4D-09 0 145.39 1.4076073035E+07 PILOT-JA 1988 940 -6.1130574598654648D+03 7.5D-07 3.4D+08 1 592.73 -6.1131344111E+03 PILOT-WE 2789 722 -2.7201075334013309D+06 3.3D-10 4.9D-05 2 4399.38 -2.7201027439E+06 PILOT4 1000 410 -2.5811392590793994D+03 2.0D-10 3.5D-09 0 324.86 -2.5811392641E+03 Log files with some details about the ALGENCAN application to each problem can be found at: http://www.ime.usp.br/~egbirgin/tango/numerical-experiments/netlib-linear-programming-problems/logfiles/ NOTE: parameters maxoutit, rhomult and rhomax mentioned above, are declared (among others) within the file algencan/sources/algconst.par.