[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: [Bug-glpk] Yet another bug found in the mip preprocessor
Date: Wed, 19 Sep 2007 13:19:59 +0400

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
341   if (a[k] > 0.0)

Andrew Makhorin

reply via email to

[Prev in Thread] Current Thread [Next in Thread]