bug-glpk
[Top][All Lists]

## [Bug-glpk] Overly restrictive assert in MIR cut generation?

 From: Tim King Subject: [Bug-glpk] Overly restrictive assert in MIR cut generation? Date: Thu, 23 Jan 2014 14:34:26 -0500

Hi glpk devs,

I think that there is an xassert that is a bit too strong in mir cut generation.  The assert is in glpio06.c in the function generate().  The assert appears in two locations for determining the "x[j]" value for ints and later the "x" value for continuous terms.  The assertion for ints is
xassert(x[j] >= -0.001);
if (x[j] < 0.0) x[j] = 0.0;
and for continuous variables is
xassert(x >= -0.001);
if (x < 0.0) x = 0.0;
This assertion is stating that the primal assignment of the variable is no more that  0.001 outside of its upper/lower bounds.  This is failing for my current problem.  I have a variable with an assignment of 22050362958990.058594 and an upper bound of 22050362958990.000000 so the assert ends up failing.  (Yes these numbers are huge.)  I've changed both of these "xassert(x[j] >= -0.001);" to "if(x < -0.001){ goto skip; }" on my copy of glpk.  Seems to do the trick, but it doesn't solve the "why is this happening?" question.

My hypothesis is that the real relaxation is not actually in bounds, but it is in bounds up to tolerance.   First, the final infeasibility is not 0. The final output of the real relaxation is "infeas =  6.250e-02 (0)".  I am still trying to understand how tot_bnd is used. I've also added some printfs to the code to try to confirm this idea. This hasn't been too success though as all I've been able to confirm is that some variables are between their upper bounds and the tolerance, but not the specific variables that are giving me trouble in mir (so no confirmation).  Any suggestions on where to decorate the code with printfs to check this would be appreciated.

Also if I enable "#define _MIR_DEBUG 1", it doesn't catch this as bad input during when it checks the upper bound.
/* check upper bound */
if (ub != +DBL_MAX)
{  eps = 1e-6 * (1.0 + fabs(ub));
xassert(mir->x[k] <= ub + eps);
}

Cheers,
--Tim King