[Couenne] Bug in adjust of branching intervals?

[Pietro Belotti]

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.;
       }

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

This seems to work for now, but let me know if it doesn't for you. Another 
(not very clean) way to solve this issue would be to perturb brpt to be 
non-integer (but still within bounds) and then let the remaining code do 
the job. I'll resort to this if the current code gives some problem.

Pietro

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

On Fri, 20 May 2011, Francois Margot wrote:

> Hi:
>
> I believe that there is a bug in
> trunk/Couenne/src/branch/CouenneBranchingObject.cpp. Around line 163, we
> have:
>
> if (integer && (::isInteger (brpt))&& (way==!
> firstBranch_))
>  brpt += 1.;
>
>
> But this is incorrect: if firstBranch_=1 and branchIndex_=0, we have
> way=1 (up branch) for the first branch and way=0 (down branch) for the
> second.
>
> if the bounds on the variable are currently [0, 2] and brpt is 1, the
> interval will be
>
> up branch: [1, 2] (correct)
> down branch: [0, 2] (incorrect, it should be [0, 0]).
>
> To fix this, brpt += 1.; should be replaced by
>
> if(way) { // up branch increase brpt
>  brpt += 1.;
> }
> else {
>  brpt -= 1.;
> }
>
> Francois
>
>
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne
>