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

[Yuri]

Andrew,

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.

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.

I use glpk-4.15.

Yuri



Quoting Andrew Makhorin <address@hidden>:

> > I have a problem that has few integer parameters defining the size
> > of the problem. It's like the large non-square underdefined linear
> > equation AX=F with extra >= conditions.
> 
> > When I downscale parameters such that problem becomes just the
> > square linear equation GLPK fails with error beginning with size
> > ~700:
> 
> >      0:   objval =   1.427134885e-02   infeas =   1.000000000e+00 (0)
> >     200:   objval =   3.448379584e-03   infeas =   3.724860891e-01 (0)
> >     203:   objval =  -7.866243389e-19   infeas =   1.314442221e-16 (500)
> > *   203:   objval =  -7.866243389e-19   infeas =   8.259452150e-16 (500)
> > *   400:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (303)
> > spx_invert: the basis matrix is ill-conditioned
> > spx_simplex: numerical problems with basis matrix
> > spx_simplex: sorry, basis recovery procedure not implemented yet
> > lpx_simplex: cannot recover undefined or non-optimal solution
> > Time used:   26.0 secs
> > Memory used: 104.3M
> 
> This a lack of the glpk simplex solver. I hope to implement a new
> version of the solver, which includes the basis recovery procedure.
> 
> > This suggests that GLPK failed to compute LU-factorization of the A
> > matrix. At the same time LAPACK package is able to find
> > LU-factorization and invert the same matrix quite easily with their
> > 'dgetrf' and 'dgetri' functions called in sequence.
> 
> > Is it reasonable to expect GLPK to invert this kind of matrices?
> > Would this be a valid enhancement request?
> 
> Ill-conditioned matrix means that its condition number is too large
> (in this case is larger than 1e12), so the solution cannot be obtained
> with a sufficient accuracy. AFAIK, dgetrf checks only for exact
> singularity, besides it uses partial pivoting. Could you estimate the
> condition number of your matrix?
> 
> >  I can provide this problem's description if necessary.
> 
> Please do that.
> 
> 
> Andrew Makhorin
> 


--