[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] [Help-glpk] [bug] glpk cycling
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] [Help-glpk] [bug] glpk cycling |
Date: |
Wed, 22 Nov 2017 23:51:13 +0300 |
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