Re: [Help-glpk] non-official updated version of glpk (4.63 pre-release)

[Andrew Makhorin]

Hi Chris,

Thank you for testing.

> I run into this behaviour with the released version as well (with a
> different MIP):
> 
>         Warning: dual simplex failed due to excessive numerical
>         instability
>         
>         
>         and later on it seems to get stuck in a sequence like:
>         *279500: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         *280000: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         *280500: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         ...
>         *9366000: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         *9366500: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         *9367000: obj =   2.196544071e+08 inf =   1.239e-13 (2)
>         and so on.
>         
> 
> 
> In this case I see the following:
> 
> Warning: numerical instability (dual simplex, phase II)
> ...
> Warning: numerical instability (dual simplex, phase II)
> Warning: dual simplex failed due to excessive numerical instability
> *4718105: obj =  -2.406747734e+06 inf =   1.988e-08 (1)
> *4999119: obj =  -2.406747734e+06 inf =   1.988e-08 (1)
> ...
> *156100559: obj =  -2.406747734e+06 inf =   1.988e-08 (1)
> *156388395: obj =  -2.406747734e+06 inf =   1.988e-08 (1)
> 
> and so on.
> 
> 
> I did some additional checking and it seems that spx_chuzc_sel finds
> an eligible variable with d[j] ~3 times the eps value but no progress
> is made, ending up cycling between two variables. 

The termination test based on a fixed tolerance value (tol_dj) currently
used in the primal simplex is not perfect. As you understand,
multiplying the objective coefficients by a constant changes the reduced
costs proportionally, so if you would multiply the objective, say, by
0.1 (for the instance above), the termination test would be passed
successfully. The internal objective scaling I added in 4.63 helps, but
not in all cases. The only way to avoid this situation is to use a more
robust termination test, for example, based on a sensitivity analysis.


Best regards,

Andrew Makhorin