Re: [Help-glpk] Explanation of Instability Warning

[Andrew Makhorin]

> I set up a Travelling Salesman Problem model using GLPK.  When I
> increase the number of cities, I run into this message:

> Warning: numerical instability (primal simplex, phase II)
> *    24: obj =   3.065645000e+06  infeas =  1.747e-20 (0)

> Could someone please tell me what this refers to and what I can do
> about it.

The warning means that due to round-off errors the current basis
became primal infesible, so the simplex solver switched to phase I
to restore primal feasibility and then continued the search.

> For example, are there parameters I can tweak to get rid of this
> message?  I am aware of glp_iocp but don't understand where its
> specific parameters can be used in the face of the issue above.

You can enable/disable the terminal output with glp_term_out routine.

> Also, after that message I get a *lot* of messages like this:

> +555052: mip =     not found yet >=   3.065645938e+06        (89009;
> 260251)
> +555716: mip =     not found yet >=   3.065645938e+06        (89070;
> 260620)
> +556402: mip =     not found yet >=   3.065645938e+06        (89158;
> 260968)

The glpk mip solver reports the search progress every 5 secs.

> Would this be related to the first problem (about numerical
> instability)?

No.

> It seems to get stuck at this point.

Your instance/formulation is hard for the glpk mip solver due to its
size and combinatorial nature.

FYI: You might try to solve tsp with Concorde using glpk as an
underlying lp solver. For more details see examples/cplex/README.


Andrew Makhorin