[Couenne] Bug in adjust of branching intervals?

[Pietro Belotti]

Good point. Fixed.

Thanks,
Pietro

--
Pietro Belotti
Dept. of Mathematical Sciences
Clemson University
email: pbelott at clemson.edu
phone: 864-656-6765
web:   myweb.clemson.edu/~pbelott

On Thu, 16 Jun 2011, Francois Margot wrote:

> 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
>>
>>
>
>