non-official updated version of glpk (4.63 pre-release)

Please see an updated version of glpk here:
http://sourceforge.net/projects/noumenon/files/tmp/
(Note that this is *not* an official release.)

The long-step technique was implemented for phase I of the primal
simplex solver. This feature can be enabled by specifying --flip option
for glpsol or by specifying glp_smcp.r_test = GLP_RT_FLIP on api level.

For many lp instances the long-step technique allows reducing the number
of simplex iterations to 30-70%; the effect is illustrated below. Note
that unlike the dual simplex, where this technique can be used on both
phase I and II, for the primal simplex it can be used only on phase I,
where the sum of primal infeasibilities (which is a convex piecewise
linear function) is minimized.

Andrew Makhorin


GLPSOL: GLPK LP/MIP Solver, v4.63
Parameter(s) specified in the command line:
 maros-r7.mps --log ns.txt
Reading problem data from 'maros-r7.mps'...
Problem: MAROS-R7
Objective: R0
3137 rows, 9408 columns, 151120 non-zeros
80307 records were read
One free row was removed
GLPK Simplex Optimizer, v4.63
3136 rows, 9408 columns, 144848 non-zeros
Preprocessing...
2152 rows, 5288 columns, 98334 non-zeros
Scaling...
 A: min|aij| =  1.672e-03  max|aij| =  1.000e+00  ratio =  5.981e+02
GM: min|aij| =  4.089e-02  max|aij| =  2.446e+01  ratio =  5.981e+02
EQ: min|aij| =  1.672e-03  max|aij| =  1.000e+00  ratio =  5.981e+02
Constructing initial basis...
Size of triangular part is 2152
      0: obj =  -8.590082000e+06 inf =   9.937e+06 (2152)
    500: obj =  -4.570998903e+06 inf =   9.082e+06 (1674) 4
   1000: obj =  -2.432982913e+06 inf =   7.605e+06 (1296) 5
   1500: obj =   1.246272826e+07 inf =   4.488e+06 (953) 5
   2000: obj =   2.626576891e+07 inf =   3.235e+06 (579) 5
   2500: obj =   3.468449326e+07 inf =   2.321e+06 (329) 4
   2958: obj =   3.334527753e+07 inf =   0.000e+00 (0) 4
*  3000: obj =   2.558273632e+07 inf =   0.000e+00 (1804)
*  3500: obj =   1.370371414e+07 inf =   0.000e+00 (1828) 5
*  4000: obj =   7.113653218e+06 inf =   0.000e+00 (1578) 5
*  4500: obj =   3.596067959e+06 inf =   0.000e+00 (1148) 5
*  5000: obj =   2.198562153e+06 inf =   0.000e+00 (1062) 5
*  5500: obj =   1.531288660e+06 inf =   0.000e+00 (280) 4
*  5822: obj =   1.497185166e+06 inf =   0.000e+00 (0) 3
OPTIMAL LP SOLUTION FOUND
Time used:   18.5 secs
Memory used: 19.7 Mb (20623887 bytes)

GLPSOL: GLPK LP/MIP Solver, v4.63
Parameter(s) specified in the command line:
 maros-r7.mps --log ls.txt --flip
Reading problem data from 'maros-r7.mps'...
Problem: MAROS-R7
Objective: R0
3137 rows, 9408 columns, 151120 non-zeros
80307 records were read
One free row was removed
GLPK Simplex Optimizer, v4.63
3136 rows, 9408 columns, 144848 non-zeros
Preprocessing...
2152 rows, 5288 columns, 98334 non-zeros
Scaling...
 A: min|aij| =  1.672e-03  max|aij| =  1.000e+00  ratio =  5.981e+02
GM: min|aij| =  4.089e-02  max|aij| =  2.446e+01  ratio =  5.981e+02
EQ: min|aij| =  1.672e-03  max|aij| =  1.000e+00  ratio =  5.981e+02
Constructing initial basis...
Size of triangular part is 2152
      0: obj =  -8.590082000e+06 inf =   9.937e+06 (2152)
    255: obj =   3.760574391e+08 inf =   0.000e+00 (0) 52%
*   500: obj =   3.331710763e+08 inf =   0.000e+00 (2106) 2
*  1000: obj =   2.857528650e+08 inf =   0.000e+00 (1834) 5
*  1500: obj =   1.687226691e+07 inf =   0.000e+00 (1769) 5
*  2000: obj =   4.909614786e+06 inf =   0.000e+00 (1467) 5
*  2500: obj =   2.780511274e+06 inf =   0.000e+00 (1526) 5
*  3000: obj =   1.699791861e+06 inf =   0.000e+00 (645) 5
*  3500: obj =   1.497291523e+06 inf =   0.000e+00 (28) 4
*  3528: obj =   1.497185166e+06 inf =   0.000e+00 (0) 1
OPTIMAL LP SOLUTION FOUND
Time used:   13.9 secs
Memory used: 19.8 Mb (20744471 bytes)