Re: [Help-glpk] glpk 4.59.2 non-official test release

[Chris Matrakidis]

Andrew,

>         Some improvements were made in the primal and dual simplex
>         solvers to make the solution process more numerically stable.

I did some testing and got several instances of cycling. I'm not sure
whether this is a new issue or whether it was uncovered from the
changes. The easiest way I found to reproduce it was using water.mps
with the long step dual simplex but I saw other instances without
--flip.

GLPSOL: GLPK LP/MIP Solver, v4.59
Parameter(s) specified in the command line:
 --pcost --cuts --flip --bfs water.mps
Reading problem data from 'water.mps'...
Problem: water
Objective: f
522 rows, 377 columns, 1642 non-zeros
154 integer variables, all of which are binary
1652 records were read
One free row was removed
GLPK Integer Optimizer, v4.59
521 rows, 377 columns, 1528 non-zeros
154 integer variables, all of which are binary
Preprocessing...
182 constraint coefficient(s) were reduced
394 rows, 321 columns, 1213 non-zeros
154 integer variables, all of which are binary
Scaling...
 A: min|aij| = 5.000e-001  max|aij| = 7.630e+004  ratio = 1.526e+005
GM: min|aij| = 4.653e-001  max|aij| = 2.149e+000  ratio = 4.619e+000
EQ: min|aij| = 2.287e-001  max|aij| = 1.000e+000  ratio = 4.373e+000
2N: min|aij| = 1.250e-001  max|aij| = 1.719e+000  ratio = 1.375e+001
Constructing initial basis...
Size of triangular part is 394
Solving LP relaxation...
GLPK Simplex Optimizer, v4.59
394 rows, 321 columns, 1213 non-zeros
      0: obj =  6.240000000e+004 inf =  8.405e+002 (9)
    125: obj =  4.174142880e+005 inf =  7.816e-014 (0)
*   218: obj =  8.685404001e+004 inf =  4.704e-013 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
WARNING: LONG-STEP DUAL SIMPLEX WILL BE USED
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
Conflict graph has 63 + 0 = 63 vertices
+   218: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: gmi = 4; mir = 28;
Warning: numerical instability (dual simplex, phase II)
+ 21182: mip =     not found yet >=  1.124708435e+005        (864; 66)
Warning: numerical instability (dual simplex, phase II)
+ 42707: mip =     not found yet >=  1.124708435e+005        (1698; 136)
+ 65182: mip =     not found yet >=  1.160667584e+005        (2538; 191)
+ 86090: mip =     not found yet >=  1.160667584e+005        (3265; 251)
Warning: numerical instability (dual simplex, phase II)
 294000: obj =  3.121033256e+008 inf =  5.425e+006 (14)
 294500: obj =  3.121033256e+008 inf =  5.425e+006 (14)
 295000: obj =  3.121033256e+008 inf =  5.425e+006 (14)
 295500: obj =  3.121033256e+008 inf =  5.425e+006 (14)
 296000: obj =  3.121033256e+008 inf =  5.425e+006 (14)
 296500: obj =  3.121033256e+008 inf =  5.425e+006 (14)
...

I also saw something similar with ns1688347 from miplib, where some
problems take a lot of time.

GLPSOL: GLPK LP/MIP Solver, v4.59
Parameter(s) specified in the command line:
 ns1688347.mps.gz
Reading problem data from 'ns1688347.mps.gz'...
Problem: ns1688347
Objective: R4192
4192 rows, 2685 columns, 66943 non-zeros
2685 integer variables, all of which are binary
76625 records were read
One free row was removed
GLPK Integer Optimizer, v4.59
4191 rows, 2685 columns, 66908 non-zeros
2685 integer variables, all of which are binary
Preprocessing...
40 hidden packing inequaliti(es) were detected
1316 hidden covering inequaliti(es) were detected
2267 constraint coefficient(s) were reduced
4191 rows, 2685 columns, 66908 non-zeros
2685 integer variables, all of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 1.000e+003  ratio = 1.000e+003
GM: min|aij| = 4.079e-001  max|aij| = 2.452e+000  ratio = 6.011e+000
EQ: min|aij| = 1.677e-001  max|aij| = 1.000e+000  ratio = 5.964e+000
2N: min|aij| = 1.250e-001  max|aij| = 1.500e+000  ratio = 1.200e+001
Constructing initial basis...
Size of triangular part is 4190
Solving LP relaxation...
GLPK Simplex Optimizer, v4.59
4191 rows, 2685 columns, 66908 non-zeros
      0: obj =  3.500000000e+001 inf =  4.438e+001 (41)
    500: obj =  3.364895672e+001 inf =  1.221e-001 (3) 3
    539: obj =  3.352941442e+001 inf =  2.412e-014 (0)
*   623: obj =  2.000000000e+000 inf =  2.751e-014 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   623: mip =     not found yet >=              -inf        (1; 0)
+  1911: mip =     not found yet >=  2.000000000e+000        (2; 0)
+  3684: mip =     not found yet >=  2.000000000e+000        (2; 0)
+  6701: mip =     not found yet >=  2.000000000e+000        (2; 0)
# 14500: obj =  1.500000000e+001 inf =  5.498e-012 (190) 77
# 15000: obj =  1.500000000e+001 inf =  6.283e-013 (120) 4
# 15500: obj =  1.500000000e+001 inf =  7.016e-013 (313) 5
# 16000: obj =  1.500000000e+001 inf =  1.507e-010 (212) 5
# 16500: obj =  1.500000000e+001 inf =  1.034e-011 (145) 5
# 17000: obj =  1.500000000e+001 inf =  1.855e-010 (499) 5
# 17500: obj =  1.500000000e+001 inf =  5.271e-011 (449) 5
# 18000: obj =  1.500000000e+001 inf =  2.697e-012 (268) 5
# 18500: obj =  1.500000000e+001 inf =  7.744e-013 (336) 5
# 19000: obj =  1.500000000e+001 inf =  9.831e-014 (257) 5
# 19500: obj =  1.500000000e+001 inf =  2.614e-011 (238) 5
# 20000: obj =  1.500000000e+001 inf =  8.323e-013 (340) 5
...
#263500: obj =  1.500000000e+001 inf =  1.244e-010 (3) 5
#264000: obj =  1.500000000e+001 inf =  1.400e-012 (6) 5
#264500: obj =  1.500000000e+001 inf =  1.128e-013 (55) 5
#265000: obj =  1.500000000e+001 inf =  8.249e-014 (140) 5
#265500: obj =  1.500000000e+001 inf =  1.594e-014 (91) 4
#266000: obj =  1.500000000e+001 inf =  6.091e-013 (9) 5
#266316: obj =  1.500000000e+001 inf =  6.831e-014 (0) 3
+266316: mip =     not found yet >=  2.000000000e+000        (3; 0)
Time used: 364.7 secs.  Memory used: 8.8 Mb.
+270473: mip =     not found yet >=  2.000000000e+000        (5; 0)
#278500: obj =  1.500000000e+001 inf =  2.407e-009 (273) 78
#279000: obj =  1.500000000e+001 inf =  7.827e-015 (128) 5
#279500: obj =  1.500000000e+001 inf =  7.788e-014 (263) 5
#280000: obj =  1.500000000e+001 inf =  9.684e-012 (324) 5
#280500: obj =  1.500000000e+001 inf =  2.295e-012 (422) 5
#281000: obj =  1.500000000e+001 inf =  1.970e-011 (251) 5
#281500: obj =  1.500000000e+001 inf =  1.269e-012 (162) 4
...
#290500: obj =  1.500000000e+001 inf =  6.692e-014 (150) 5
#291000: obj =  1.500000000e+001 inf =  1.176e-014 (264) 4
#291500: obj =  1.500007229e+001 inf =  1.459e-012 (152) 5
#291810: obj =  1.500007283e+001 inf =  3.066e-013 (0) 3
+291810: mip =     not found yet >=  2.000000000e+000        (6; 0)
+292194: mip =     not found yet >=  2.000000000e+000        (13; 0)
+292307: mip =     not found yet >=  2.000000000e+000        (20; 0)
+292325: mip =     not found yet >=  2.000000000e+000        (27; 0)
...

ns1688347 was one of the problems that had issues with the previous
simplex code but not at this point:
...
Integer optimization begins...
+   623: mip =     not found yet >=              -inf        (1; 0)
+  1911: mip =     not found yet >=  2.000000000e+000        (2; 0)
+  3684: mip =     not found yet >=  2.000000000e+000        (2; 0)
+  6701: mip =     not found yet >=  2.000000000e+000        (2; 0)
+ 10099: mip =     not found yet >=  2.000000000e+000        (6; 0)
+ 10131: mip =     not found yet >=  2.000000000e+000        (15; 0)
+ 10141: mip =     not found yet >=  2.000000000e+000        (24; 0)
...


Best Regards,

Chris Matrakidis