Re: [Help-glpk] GLPK failure to invert matrix

[Andrew Makhorin]

> I accidentally lost the original testcase that was giving
> 'spx_invert: the basis matrix is ill-conditioned', will try to
> restore it.

> But here is attached a very similar testcase that is being solved
> wrong.

> When NPROB := 512 solution is correct. But when I make NPROB := 513
> solution is wrong, it becomes all zeros. Correct solution is always
> x[21]=1, all others are 0.

If the simplex solver fails, it sets the solution status to UNDEFINED,
in which case primal and dual values of all variables are set to zero.
Unfortunately, a feature to check the solution status in the MathProg
model is not implemented yet.

> I believe original failure was also related to 512->513 size change.
> But for some reason spx_invert doesn't fail any more, instead I am
> getting the wrong solution. I will try to also restore the original
> testcase.

It seems the lp presolver does not provide sufficient accuracy.

I set up NPROB := 513 and disabled the presolver (--nopresol), and
glpsol found optimal solution with no numeric difficulties.

Model has been successfully generated
dmp_create_pool: warning: debug mode enabled
lpx_adv_basis: size of triangular part = 2
      0:   objval =   2.541424758e+01   infeas =   1.000000000e+00 (0)
    200:   objval =   2.992014283e-01   infeas =   3.640391721e-02 (0)
    400:   objval =   2.287132151e-01   infeas =   3.382184648e-02 (0)
    506:   objval =   1.000000000e+00   infeas =   0.000000000e+00 (6)
*   506:   objval =   1.000000000e+00   infeas =   0.000000000e+00 (6)
*   512:   objval =   1.000000000e+00   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   28.0 secs
Memory used: 68.6 Mb (71926621 bytes)

   20 x[20]        B              0
   21 x[21]        B              1
   22 x[22]        B              0

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 3.98e-16 on row 26
        max.rel.err. = 3.66e-16 on row 26
        High quality

KKT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err. = 9.53e-15 on column 490
        max.rel.err. = 4.77e-15 on column 490
        High quality

KKT.DB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

Hmm...

(ten minutes gone)

The lp presolver works correctly. The instability appears due to an
inappropriate initial basis. If I specify the standard initial basis
of all slacks (--std), glpsol solves correctly your model even if the
lp presolver is enabled.

Thank you for your example.

Andrew Makhorin

PS: I removed the attachment from your message due to its size (6MB).