Re: [Help-glpk] Another numerical instability warning

[Andrew Makhorin]

Hi Robbie,

> This is more an observation than a question.
> 
> After adding the following entry to the GLPK wikibook:
> 
>   http://en.wikibooks.org/wiki/GLPK/Troubleshooting#Numerical_instability
> 
> I ran into almost the same problem -- but this time
> dual not primal:
> 
>   Warning: numerical instability (dual simplex, phase II)
> 
> This particular warning is not documented in the API
> manual but I guess what was said earlier about the
> primal warning also applies.
> 

In the primal simplex some basic variables may violate their lower or
upper bounds within a tolerance; similarly in the dual simplex some
non-basic variables may have wrong reduced costs again within a
tolerance. This is normal. However, due to accumulating round-off errors
it may happen than the violation exceeds the tolerance, in which case
the solution is considered as primal (dual) infeasible, and the glpk
simplex solver issues the warning message about numerical instability.
There exist two ways to restore feasibility: immediately by swithing to
phase I (as glpk currently does) and by relaxing violated bounds (or
objective coefficients in the dual case). The latter way seems to be
better except its one disadvantage that some bounds (objective
coefficients) may remain relaxed at the final point, in which case we
need to restore original bounds and then apply the dual (or primal)
simplex to find the true optimum. Currently I'm working on a new
implementation of the simplex solver, where (among other improvements) I
decided to use bound relaxation, because this also helps against
stalling. So, that notorious warning message will disappear in the new
version.


Andrew Makhorin