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 _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
