[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
#endif
341 if (a[k] > 0.0)
Andrew Makhorin
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Bug-glpk] Yet another bug found in the mip preprocessor,
Andrew Makhorin <=