On bmibnb's branching strategy

[wuhua hu]

Solving a bilinear problem to global optimality is challenging in general. The literature [1] shows that it can considerably expedite the solution searching process by restricting branching to only a set of the variables of a small dimension when there are other sets of variables that have much higher dimensions. That is, given two vectors of variables x and y, dimension(x) << dimension(y), we restrict the branching to occur only on x (It is proved that the branch and bound algorithm converges ).

Johan, has the current solver 'bmibnb' implemented such a capability with proper setting, or is it easy to modify the solver's source code to enable such a function? Could you help clarify or give any cue to do the modification if that is possible? I am stuck by the difficulty of solving a large-scale bilinear problem to global optimality.

[1] Manmohan Chandraker, and David Kriegman, Globally Optimal Bilinear Programming for Computer Vision Applications, CVPR, 2008. (URL: https://www.google.com.sg/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&ved=0CEIQFjAB&url=http%3A%2F%2Fvision.ucsd.edu%2F~manu%2Fpdf%2Fcvpr08_bilinear.pdf&ei=hg_oUOrsE4nilAXZooHIBg&usg=AFQjCNFcsvGR4KCU533fc_xtAIzmIih7Xg&sig2=hR6aHLJjas3lopWnYFIcsw&bvm=bv.1355534169,d.bmk)

[Johan Löfberg]

Yes, it is obtained by using the lowrank option. It does not necessarily help much though, since the basic variable selection that is used often selects these variables anyway.

 x = sdpvar(4,1);

 y = sdpvar(20,1);

 obj =  sum(sum(randn(20,4).*(y*x')))

 ops = sdpsettings('solver','bmibnb');

 solvesdp([-1 <= [x;y] <= 1],obj,ops);

 ops = sdpsettings('solver','bmibnb','bmibnb.lowrank',1);

 solvesdp([-1 <= [x;y] <= 1],obj,ops)

[Wuhua Hu]

I see, Johan. Then, a further question: 

What will the partition be if there are three sets of variables, say, x \in R^n, y \in R^m, z \in R^k, satisfying n<<m and n<<k, while the bilinear terms are y(i)*x, z(j)*x, where i = 1, 2, ..., m and j = 1, 2, ..., k? Will the branching always be restricted to x (which is I want to try, by referring to the attractive performance as shown in the literature [1])?

(As introduced for the solver: "bmibnb.lowrank - Partition variables into two disjoint sets and branch on smallest" (if set to 1).)

[Johan Löfberg]

Yes, it computes a bi-partite structure and branches on the smallest member (x).

[Wuhua Hu]

Got it. Thank you so much!

With the function switched on, the tests show that the solver works a bit faster on average but is yet hopeless to solve my problem with the variables x in R^3, y in R^10 and z in R^10, when both the objective and the constraints contain the aforementioned bilinear terms. (And the actual problem I need to solve has variables x in R^3, y in R^100+ and z in R^100+.)

Do you know any way to solve such a 'large-scale' bilinear problem to global optimality or good sub-optimality subject to an acceptable computational time (say, within hours' time)?

[Johan Löfberg]

You are welcome to send the model to me for further analysis.

[Wuhua Hu]

As the problem model would be used for a funding application, it has to be kept secrete at the current stage. I would contact you if that were allowed in the future. Appreciate your help and interest!

[Johan Löfberg]

Just create a similiar completely anonymous model.

[Wuhua Hu]

Ok, I would try and send it to you.