Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering of variables]

[Andrew Makhorin]

> My application creates lots of flow network problems,
> some are max-flow, some are min-cost. This one is
> min-cost.
> 
> I have been recovering spurious results whenever I hit
> the following problem:
> 
>   Warning: numerical instability (dual simplex, phase II)

Your instance is badly scaled:

>  A: min|aij| =  4.649e-08  max|aij| =  2.967e+08  ratio =  6.383e+15

In this case using the geometric mean scaling is not reliable, so I'd
suggest either to use only the equilibration scaling, or do not use the
scaling at all.

You might remove tiny constraint coefficients by replacing them with
exact zeros (looks like they are result of computations, where numeric
cancellation does not occur due to round-off errors). However, if tiny
constraint coefficients are result of using a "big M", then your M is
too big.

In many cases a badly scaled instance leads to ill-conditioned basis
matrices, in which case it is impossible to find basic solutions with
sufficient accuracy.

PS: Your problem does not look like mincost. Any mincost problem has a
0-1 constraint matrix, which is the incidence matrix of a network.