Re: [Bug-glpk] [Help-glpk] [bug] glpk cycling

[Andrew Makhorin]

On Wed, 2017-11-22 at 22:13 +0300, Andrew Makhorin wrote:
> On Wed, 2017-11-22 at 16:13 +0100, David Monniaux wrote:
> > On 22/11/2017 13:46, Andrew Makhorin wrote:
> > >
> > > Please write the instance to a text file in lp format (with
> > > glp_write_lp) or better in glp format (with glp_write_prob) and post it
> > > either to the bug-glpk list or to me. Thanks.
> > 
> > Mmh. We use a fairly recent version of g++ I think, this may have a
> > libstdc++ with different regexp. Can you please try with g++ 6 or 7?
> > 
> > The problem is that if we save to a file and resolve from the file, it
> > works ok; thus we cannot follow your suggestion.
> > 
> > As seen in the source code, we solve a problem several times with
> > slightly altered coefficients. Thus, the simplex tableau is, when the
> > cycling condition is encountered, not in the state one would obtain by
> > starting from scratch.
> > 
> > We see:
> > 
> > #    18: obj =   0.000000000e+00 inf =   0.000e+00 (2)
> > Perturbing LP to avoid stalling [217]...
> > #1411638: obj =   0.000000000e+00 inf =   0.000e+00 (4) 12065
> > #2864142: obj =   0.000000000e+00 inf =   0.000e+00 (3) 12414
> > and so on
> > 
> > Regards
> > 
> 
> Thank you. Looks like a bug in the dual simplex solver. I need a time to
> investigate it.
> 
> I found that the instance is solved successfully if I call
> glp_std_basis(glp) or glp_adv_basis(glp, 0) immediately before the call
> to glp_simplex. This indicates a basis issue, however, does not explain
> why the dual solver fails.
> 

Please change the routine play_coef in file glpk/src/simplex/spydual.c
as follows:

change #if 1 to #if 0 in lines 944-948:

#if 0 /* 12/VII-2017 */
                  c[k] -= d[j], d[j] = 0.0;
#else
                  c[k] -= d[j] - 1e-9, d[j] = +1e-9;
#endif

similarly, change #if 1 to #if 0 in lines 962-966:

#if 0 /* 12/VII-2017 */
                  c[k] -= d[j], d[j] = 0.0;
#else
                  c[k] -= d[j] + 1e-9, d[j] = -1e-9;
#endif

Since in your instance the objective is zero, the current version of
play_coef intended to perturb the objective coefficients doesn't work.

Hope this helps.


Andrew Makhorin