[Couenne] Bug in adjust of branching intervals?

[Francois Margot]

Pietro:

There is still a bug.

On Sat, 2011-05-21 at 22:34 +0200, Pietro Belotti wrote:
> Francois,
> 
> 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:
> 
>    if (integer &&
>        ::isInteger (brpt)) {
> 
>      // Look at all possible cases (l,u are
>      // bounds, b is the branching point. l,u,b all integer):
>      //
>      // 1) l <  b <  u: first branch on b +/- 1 depending on branch
>      // direction, second branch on b;
>      //
>      // 2) l <= b <  u: LEFT branch on b, RIGHT branch on b+1
>      //
>      // 3) l <  b <= u: LEFT branch on b-1, RIGHT branch on b
> 
>      assert ((brpt - l > .5) ||
>  	    (u - brpt > .5));
> 
>      if ((brpt - l > .5) &&
>  	(u - brpt > .5)) { // brpt is integer interior point of [l,u]
> 
>        if (firstBranch_) {
>  	if (!way) brpt -= 1.;
>  	else      brpt += 1.;
>        }
> 

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.

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(). 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.

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.

Francois