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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
