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

[Andrew Makhorin]

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.


Andrew Makhorin