Re: [Bug-glpk] glp_intopt recovery feature added

[Andrew Makhorin]

> > > Also attached is a model in free mps format that illustrates the effect.
> > > (This model looks "innocent", but it has some pathological properties
> > > that makes it very hard to solve with glpk.)
> > 
> > This model is quite useful to demonstrate issues with the solver.
> 
> In this case all the issues are caused by inappropriate pivot choice in
> the dual simplex solver. For example, decreasing piv_tol from 1e-9
> (default) to, say, 1e-6, prevents the basis to be ill-conditioned and
> makes the solution process stable; however, sometimes this leads to
> skipping significant constraints, that in turn, causes numerical
> instability (i.e. excessive bound violation).
> 

Evidence:

GLPSOL: GLPK LP/MIP Solver, v4.59
Parameter(s) specified in the command line:
 C:/temp/fails/water.mps --flip --pcost --mir
Reading problem data from 'C:/temp/fails/water.mps'...
Problem: water
[...]
MIR cuts enabled
+   221: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: mir = 28;
[...]
best_ratio = 5.8484e-07
best_ratio = 2.1089e-15   <--- this causes error
Error: unable to factorize the basis matrix (1)
Constructing initial basis...
[...]

Best_ratio is |t[p,q]| / max |t[p,*]|, where t[p,*] is p-th row of the
simplex tableau used to choose a non-basic variable xN[q] in the dual
simplex. Currently the solver makes up to 5 attempts to choose an
appropriate column, i.e. having not too small pivot, but the pivot
magnitude is not checked.