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

[Andrew Makhorin]

Hi Chris,

Thank you for testing.

> >         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.

I don't think that --flip causes instability. Water.mps is a hard
instance that has bad numerical properties (due to big-M formulation 
I think).

I tried solving it in the following way. First I used --bestp to find a
feasible solution quickly and save it to a file:

GLPSOL: GLPK LP/MIP Solver, v4.59
Parameter(s) specified in the command line:
 water.mps --flip --mir --bestp --save sol --log log1
Integer optimization begins...
WARNING: LONG-STEP DUAL SIMPLEX WILL BE USED
MIR cuts enabled
+   221: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: mir = 28;
Cuts on level 75: mir = 49;
+  1744: >>>>>   4.112932007e+05 >=   9.209365003e+04  77.6% (82; 2)
Writing MIP solution to 'sol'...
[...]
+ 19375: >>>>>   3.975897518e+05 >=   9.209365003e+04  76.8% (1008; 94)
Writing MIP solution to 'sol'...
[...]
+245892: >>>>>   3.377437093e+05 >=   9.209365003e+04  72.7% (12241;
1660)
Writing MIP solution to 'sol'...
[...]

And then I used that solution as an incumbent value trying to "prove"
its optimality:

GLPSOL: GLPK LP/MIP Solver, v4.59
Parameter(s) specified in the command line:
 water.mps --flip --cuts --use sol --log log2 --nointopt
[...]
+   191: mip =   3.377437093e+05 >=              -inf        (1; 0)
Cuts on level 0: gmi = 3; mir = 23; cov = 2;
+  8751: mip =   3.377437093e+05 >=   9.302734375e+04  72.5% (492; 14)
[...]
+226198: mip =   3.377437093e+05 >=   1.204208365e+05  64.3% (12991;
506)
[...]

However, the integrality gap is large and decreases very slowly.

> + 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 think this happens because of Gomory's cuts. Sometimes such cuts
become almost linear dependent and thereby cause numerical problems.

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

It is also a hard (for glpk) instance due to big-M formulation.

> +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

This is not a cycling. This is an output from the dual simplex. It
starts if the solution of the current node takes more than 10 secs.


Best regards,

Andrew Makhorin