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

[Chris Matrakidis]

Andrew,

A "smart" LP perturbation was also implemented in the dual simplex
solver. This feature is similar to the one implemented in the primal
simplex solver (see below).

I did some testing of this and it seems like the dual simplex is less stable than the previous version.

An example to see this is problem sp98ir from miplib 2010. Trying to solve this with --pcost I see lots of warnings like:
Warning: numerical instability (dual simplex, phase II)
or:
Warning: numerical instability (dual simplex, phase I)
and finally:
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.

With version 4.62 this problem is solved rather quickly with only a few occasional:
Warning: numerical instability (dual simplex, phase II)

messages.

Best Regards,

Chris Matrakidis