Re: [Bug-glpk] internal error: row->lb != row->ub

[Hermann Schwarting]

Am Donnerstag, 8. November 2007 schrieb Andrew Makhorin:

> In fact, the bug appears in the lp presolver (which is part of
> glpk) due to its insufficient robustness. Most probably this
> happens because some equality constraints in your model have
> extremely small (in magnutude) right-hand sides, for example:
> [...]
> 
> I think the bug will disappear if you replace such rhs by exact
> zeros.

Hi,

you're right, these very small values are irrelevant and can be 
replaced by zero without effect on the total result. I'll use this 
workaround. What puzzled me though was that other 300 cases worked 
well and all contain similarly small values. I looked deeper into it 
and found that of the test case I sent in the original post exactly 
one constraint is the culprit and triggers the assertion:

r_123: + x_9506 + x_9367 + x_9228 + x_9089 + x_8950 + x_8811 + x_8672
+ x_8533 + x_8394 + x_8255 + x_8116 + x_7977 + x_7838 + x_7699
+ x_7560 + x_7421 + x_7282 + x_7143 + x_7004 + x_6865 + x_6726
+ x_6587 + x_6448 + x_6309 + x_6170 + x_6031 + x_5892 + x_5753
+ x_5614 + x_5475 + x_5336 + x_5197 + x_5058 + x_4919 + x_4780
+ x_4641 + x_4502 + x_4363 + x_4224 + x_4085 + x_3946 + x_3807
+ x_3668 + x_3529 + x_3390 + x_3251 + x_3112 + x_2973 + x_2834
+ x_2695 + x_2556 + x_2417 + x_2278 + x_2139 + x_2000 + x_1861
+ x_1722 + x_1583 + x_1444 + x_1305 + x_1166 + x_1027 + x_888
+ x_749 + x_610 + x_471 + x_332 + x_193 + x_54 = 1.00085889924773e-07

If I replace this one value with zero the problem disappears. Looking 
closer at the code in glplpp02.c lines 1523--1543 you find the 
following:


/* check if the row is implicitly fixed on its upper bound */
if (row->ub != +DBL_MAX)
{  eps = 1e-7 * (1.0 + fabs(row->ub));
 if (lb >= row->ub - eps)
 {  process_forcing_row(lpp, row, 1);
    goto done;
 }
}
/* check whether the row can reach its lower bound */
if (row->lb != -DBL_MAX)
{  eps = 1.001e-7 * (1.0 + fabs(row->lb));
 if (lb >= row->lb - eps)
 {  /* the row cannot reach its lower bound, so the lower bound
       is redundant and therefore can be removed (note that the
       row cannot be an equality constraint at this point, since
       the case l' > u[p] = l[p] would be processed above */
    xassert(row->lb != row->ub);
    row->lb = -DBL_MAX;
    lpp_enque_row(lpp, row);
 }
}

While running through these lines, the lb is 0, ub is 1.7...e+308 and 
row->lb == row->ub == 1.00085...e-07. In the first if-clause eps is 
1.000000100085...e-07 and (lb >= row->ub - eps) is false. In the 
second if-clause eps is 1.001000100185...e-07 and the test (lb >= 
row->lb - eps) succeeds because row->lb - eps < 0 even though row->lb 
is equal to row->ub, which then triggers the assert.

Not knowing anything about the intricacies of floating point math, I 
don't understand the motivation for the different choices of eps. But 
I guess eps is the problem here. Whenever the bound is between 
1.0000001e-7 and 1.001e-07 the assertion is triggered.

Kind regards,
Hermann