[Couenne] balanced branching strategy in couenne

[Pietro Belotti]

Hi Pete,

all powers x^k with k odd (or with odd inverse, such as x^(1/3)),  
having inflection points, are treated depending on the lower and upper  
bounds on x. See Couenne/src/branching/operators/branchExprPow.cpp,  
lines 229-285 (and 290-345 for the odd inverse case). In the balanced  
case, the procedure computing the branching point is at  
Couenne/src/branching/operators/minMaxDelta.cpp, line 48.

With inflection points, the distances should be computed correctly in  
the general case, but you are right in that there might be particular  
cases where this doesn't work: it may either not compute a really  
balanced branching rule or trigger an exception when computing the  
square root of a negative number (this would happen at  
Couenne/src/branching/operators/minMaxDelta.cpp line 37).

The default branching strategy though (mid-point) is also good, and in  
fact we didn't notice significant differences in performance between  
the two, so I'd suggest you try that.

Thanks very much for pointing this out. I'll submit a ticket so that  
it gets in the pipeline and hopefully solved soon.

Cheers,
Pietro

_________________________________________
Pietro Belotti, Lehigh University
Dept. of Industrial and Systems Engineering
200 W Packer Ave, Bethlehem PA 18015.
phone: 610-758-3865   fax: 610-758-4886
email: belotti at lehigh.edu
web:   http://www.lehigh.edu/~pib208


On 02/20/2010, Pete Janes <ppjanes at gmail.com> wrote:

> Hi Pietro,
>
> I am looking at the procedure for the balanced branching strategy in Couenne.
> I undertand that it computes the branching point which minimizes the  
> differences
> in the distance between LP1 and the primal function, and LP2 and the
> primal function.
> Where LP1 and LP2 are the two LP's to be generated by the  
> hypothetical branch.
>
> Looking at the code, it appears that this procedure assumes that the
> primal function
> is uniformly convex or concave - as the LP are taken to be the line
> segment from
> the two end points of the primal function. However, in Couenne,
> functions such as
> x^3 also uses the balanced branching strategy, and it has an  
> inflection point.
>
> Can this be problematic in some isolated cases? (I am currently
> implementing a relaxation
> for a univariate function that has one saddle point) Should I use a
> simpler strategy just in
> case?
>
> Kind regards,
>
> Pete
>



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.