[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] internal error: row->lb != row->ub
From: |
Hermann Schwarting |
Subject: |
Re: [Bug-glpk] internal error: row->lb != row->ub |
Date: |
Sat, 10 Nov 2007 17:39:49 +0300 |
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