Re: [Bug-glpk] numerical instability (cycling?)

[Andrew Makhorin]

Hi Ali,

> I suspect that i have ill-conditioned / badly scaled LP problems.

> They should be either solved in a few iterations starting from a given
> initial basis or the solver should return that the problem is
> ill-conditioned / badly scaled and has given up the procedure.
> Unfortunately my LP problems make the solver hang up, from the output
> it seems to me that the simplex algorithm is cycling.

> How can i dump these LP problems so that this phenomenon can be
> reproduced on different machines?

> I tried:

> parm.msg_lev = GLP_MSG_ALL;
> glp_term_out(GLP_ON);
> glp_write_lp(lp, 0, "dump.lp");
> glp_write_sol(lp, "dump.bas");

> right before the critical call to glp_simplex.

> These files and the output are here:

> http://reliablecomputing.eu/glpk/dump.lp
> http://reliablecomputing.eu/glpk/dump.bas
> http://reliablecomputing.eu/glpk/console

> As for the output, the objective consists of a single variable. The LP
> problems are generated using the C API.

I cannot reproduce the bug. Even with options --nopresol and --noscale
glpsol successfully solves your instance:

GLPSOL: GLPK LP/MIP Solver 4.40
Reading problem data from `dump.lp'...
400 rows, 640 columns, 1678 non-zeros
1568 lines were read
Constructing initial basis...
Size of triangular part = 400
      0: obj =  -1.000000000e+00  infeas =  2.449e+01 (0)
    200: obj =  -1.000000000e+00  infeas =  3.644e-02 (0)
*   369: obj =  -9.717267586e-01  infeas =  1.321e-13 (0)
Warning: numerical instability (primal simplex, phase II)
    388: obj =  -9.736242870e-01  infeas =  9.841e-07 (0)
*   389: obj =  -9.736242870e-01  infeas =  1.981e-13 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.5 Mb (483719 bytes)

You could try to use a more stable form of the basis factorization,
for example, bfcp.type = GLP_BF_GR (that corresponds to glpsol
option --cgr) with the api routines glp_get_bfcp/glp_set_bfcp. This
may help.


Andrew Makhorin