[Bug-glpk] Yet another bug found in the mip preprocessor

[Andrew Makhorin]

Yet another bug has been detected in the mip preprocessor, due to which
constraint coefficients with small magnitude can lead to wrong implied
bounds of structural variables that, in turn, can cause prematurely
pruning some branches of the search tree, in which case final solution
will be worse than the exact optimum.

To fix the bug please insert the following lines to the internal routine
col_implied_bounds (file glpios02.c):

340   /* determine implied bounds of x[k] (16) and (17) */
#if 1
+++   /* do not use a[k] if it has small magnitude to prevent wrong
+++      implied bounds; for example, 1e-15 * x1 >= x2 + x3, where
+++      x1 >= -10, x2, x3 >= 0, would lead to wrong conclusion that
+++      x1 >= 0 */
+++   if (fabs(a[k]) < 1e-6)
+++      *ll = -DBL_MAX, *uu = +DBL_MAX; else
#endif
341   if (a[k] > 0.0)


Andrew Makhorin