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)
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
