[Couenne] Bug in adjust of branching intervals?

[Francois Margot]

Pietro:

Still a bug. In CouenneBranchingObject.cpp around line 165, we have:

    if ((brpt - l > .5) &&
	(u - brpt > .5) && // brpt is integer interior point of [l,u]
	!branchIndex_) { // if this is the first branch operation

      if (!way) brpt -= (1. - COUENNE_EPS);
      else      brpt += (1. - COUENNE_EPS);
    } 

    else if (u - brpt > .5) {if  (way) brpt += (1. - COUENNE_EPS);} 
    else if (brpt - l > .5) {if (!way) brpt -= (1. - COUENNE_EPS);}

But the test on branchIndex_ should be separated from the other two
tests, i.e.:

    if ((brpt - l > .5) &&
	(u - brpt > .5)) { // brpt is integer interior point of [l,u]

      if(!branchIndex_) { // if this is the first branch operation

        if (!way) brpt -= (1. - COUENNE_EPS);
        else      brpt += (1. - COUENNE_EPS);
      } 
    }
    else if (u - brpt > .5) {if  (way) brpt += (1. - COUENNE_EPS);} 
    else if (brpt - l > .5) {if (!way) brpt -= (1. - COUENNE_EPS);}

Otherwise, in the case where l < brpt < u, the branching point is
modified in both branches.

Francois


On Sun, 2011-06-12 at 11:37 +0200, Pietro Belotti wrote:
Francois,
> 
> this should be fixed now.
> 
> >> I think there is indeed a bug. However, the solution you propose
might 
> >> introduce another bug, especially if brpt is equal to one of the 
> >> bounds. I am going to commit the following (hopefully
comprehensive) 
> >> code:
> >>
> >> [...]
> >
> > The above is incorrect. The condition if(firstBranch_) should be
> >
> > if(!branchIndex_) {
> >
> > firstBranch_ indicates the direction of preferred branching, it has
the 
> > same value in all branches. The above code adjusts the branching
point 
> > in both branches, resulting in one integer value being excluded
from 
> > both.
> 
> I'm now using branchIndex_, thanks for pointing that out.
> 
> > In addition, due to rounding error, replacing
> >
> > brpt -= 1.; (resp. brpt += 1.;)
> >
> > by brpt -= 0.99999; (resp. brpt += 0.99999;)
> >
> > avoids the disappearance of some integer values in both branches.
Maybe 
> > the value delta = 0.99999 should be related to the tolerance used
in 
> > isInteger().
> 
> Given the further rounding performed by bound tightening and
branching 
> itself, I believe a (1. - COUENNE_EPS) should suffice.
> 
> > If isInteger(a)==true with closest integer value b, then we 
> > must have (a-delta) > b-1 and (a+delta < b+1).
> >
> > Also, just below,
> >
> > else if (u - brpt > .5) {if  (way) brpt += 1.;}
> > else if (brpt - l > .5) {if (!way) brpt -= 1.;}
> >
> > the value 1. should also be replace by delta.
> 
> Done.
> 
> > Finally some thoughts should be devoted to the case
> >
> >  if ((brpt < l) || (brpt > u))
> >    brpt = 0.5 * (l+u);
> >
> > If the violation of the bounds is small and (l+u) is huge, it might
be
> > better to alter brpt slighlty than taking the midpoint. Also, if the
> > variable is integer and (l+u) is a multiple of 2, the two branches
will
> > share a value.
> 
> The current code eliminates that value and should also take care of
large 
> bounds (where "large" is now any value whose absolute value is above
1e9).
> 
> Pietro
> 
>