Re: [Bug-glpk] bug in spx_prim_chuzr and solution

[Andrew Makhorin]

>I found a rather rare bug in spx_prim_chuzr.
>
>If all elements of the q-th column of the simplex table are too small,
>ret is set to 1 to tell the calling routine to reinvert the basis (which
>is currently not implemented and causes an error).
>
>But if (typx[k] == LPX_DB) this is OK and should not cause concern.
>
>I suggest the following modification at line 740:
>
>      if (typx[k] == LPX_DB)
>      {  /* xN[q] has both lower and upper bounds */
>         p = -1, p_tag = 0, teta = (ub[k] - lb[k]) + relax, big = 1.0;
>         ret = 0; //<- added line
>      }
>
>This logic error may exist in similar routines used in the dual variant
>of the simplex method but I have not checked.  I came across it while
>solving a very simple problem with one constraint!

Thank you for your bug report.

That bug was already reported and I'll fix it in the next release. In
fact, if an LP problem has a double-bounded column that has non-zero
objective coefficient and all its constraint coefficients are zero,
being chosen it causes ret = 1, because the correspoding column of the
tableau is obviously zero, in which case the routine spx_prim_chuzr
erroneously concludes that that column has insufficient numerical
accuracy and the primal ratio test might be unreliable.

To fix that bug please replace the statement placed in the routine
spx_prim_chuzr (file 'glpspx2.c', line 734):

      if (big < lp->tol_piv) ret = 1;

by the following:

      if (big < lp->tol_piv) ret = 0;

or just remove the entire line. This allows to by-pass the check, which
causes the error.