branching strategy in BnB

[Yujia Wang]

Hi Johan,

I'm trying to understand bmibnb better.  Is there any documentations on the branching strategy used in the yalmip implementation of BnB?  If not, could you please give a very brief overview? 

[Johan Löfberg]

You talk about bmibnb first, and then bnb. Which do you mean?

[Yujia Wang]

Sorry, I meant bmibnb.

[Johan Löfberg]

After solving a relaxation in a node, the relaxed variables w_i which differ most from the function it relaxes, f_i(x), is detected, i.e., i = max_i (|w_i-f_i(x)|) is found. Of the involved variables in f_i(x), the variable with the largest interval is branched. The new intervals are based on dividing the old interval in two equally large parts

[Yujia Wang]

Thanks for the information!  What happens with the other relaxed variables w_k that also shows a large difference from f_i(x), but not the largest?  

[Johan Löfberg]

They will be branched upon somewhere deeper down the tree, since we always branch on the variables in the largest gap (since when we branch on a set of variables, the function they are used in will have a decreased gap and hence typically not branched upon in the next level, or at least not in many levels in a row)

[Yujia Wang]

Got it, thank you!