how to use branch and bound method in a mixed integer LP problem

[Jason]

Dear Johan,

Could you help me with how to use your bnb code to solve a mixed integer LP problem. I want the bnb to branch on binvar z1 , z2 and find the most approriate value of z1,z2. But with the current code (see below), the method gives the result directly and there don't have any branch and bound.The computation result of limpr is right, but i don't get the right answer of z1 and z2.  For now, I don't know where goes wrong, could you help me? Thank you in advance!

* Starting YALMIP integer branch & bound.
* Lower solver   : LINPROG
* Upper solver   : rounder
* Max iterations : 300
 Node       Upper       Gap(%)      Lower    Open
    1 :   8.612E+000     0.00     8.612E+000   0  Successfully solved
+   1 Finishing.  Cost: 8.6117



/ code
{
          limpr=sdpvar(S*A,1);    
          z1=binvar(n+1,1);
          z2=binvar(n+1,1);       
          F=[Aeq*limpr==beq,limpr>=0,sum(z1)==1,sum(z2)==1];
          lpmat=reshape(sum(reshape(limpr,A,S)),n+1,[]); 
          SumofSet1=transpose(fliplr(cumsum(fliplr(sum(lpmat)))));
          SumofSet1(1)=[];
          SumofSet1(end+1)=0;
         
          SumofSet2=flipud(cumsum(flipud(sum(lpmat,2))));
          SumofSet2(1)=[];
          SumofSet2(end+1)=0;
         
          F=[F,SumofSet1<=ones(n+1,1)-z1+1e-5,SumofSet2<=ones(n+1,1)-z2+1e-5];
          obj=f'*limpr;
          ops=sdpsettings('solver','bnb','bnb.branchrule','max','bnb.method','breadth','bnb.solver','linprog');
          optimize(F,obj,ops);
          pi=value(limpr); 

}

[Johan Löfberg]

First, you should install a real MILP solver. No reason to use bnb+linprog

Secondly, we have no telepathics here, no one  knows what you think is right or wrong, or what you have obtained.

[Jason]

Thank you. LOL. But, I have already installed CPLEX in my computer. The confusion is I don't know in the bnb code how it choose variables to branch and to bound.

[Johan Löfberg]

As you have specified it, it choses the binary variable which is furthest away from being binary when the relaxation is solved.

However, your milp is so trivial that it doesn't have to branch. The root relaxation is binary feasible.

[Jason]

Yes, you're right. Actually, this problem can be solved using LP methods. But, I want to try the mixed integer LP formulation which included the binary variables, to see whether it's result is close to LP formulation and compare their computation time.
Comtraints 1-3 are included in the primal LP formulation,  then I introduced binary variable Z with constraints 4-5 to change to MILP formulation.

[Johan Löfberg]

So what is the actual question then. You knew the MILP forumulation is tight and thus cannot generate any branching, so why are you asking on what variables branching is performed.

[Jason]

Yes. But, could you see again the constraints below. I want the last two constraints find the fist zero of variables SumofSet1 and SumofSet2, then set the corrsponding z1,z2 equal to 1. This means I should branch at the first value of z1, then the second value, until I find in which element of z1 it should be one (for example the sixth element of SumofSet1 is 0, then the correspongind sixth element of z1 equals to one. because i use the cumsum function, the 7th element until the end of SumofSet1 are all equal to zero, but we set the corresponding z1 to zero.) Then, we branch the first value of z2 until find the first element which should be one. But, the current code, every time it sets the last number of z1 and z2 to 1, which also meets the constriants, but is not i wanted.

在此输入代码...

limpr=sdpvar(S*A,1);    
z1=binvar(n+1,1);
z2=binvar(n+1,1);        
F=[Aeq*limpr==beq,limpr>=0,sum(z1)==1,sum(z2)==1];

lpmat=reshape(sum(reshape(limpr,A,S)),n+1,[]);  
SumofSet1=transpose(fliplr(cumsum(fliplr(sum(lpmat)))));
SumofSet1(1)=[];
SumofSet1(end+1)=0;
         
SumofSet2=flipud(cumsum(flipud(sum(lpmat,2))));
SumofSet2(1)=[];
SumofSet2(end+1)=0;

         
F=[F,SumofSet1<=ones(n+1,1)-z1+1e-8,SumofSet2<=ones(n+1,1)-z2+1e-8];
obj=f'*limpr;
ops=sdpsettings('solver','bnb','bnb.branchrule','max','bnb.method','breadth','bnb.solver','linprog');
optimize(F,obj,ops);

[Johan Löfberg]

What do you mean you should branch on the first value of z1? bnb simply branches on any binary variable it deems being most beneficial to branch on, using the trivial strategy of branching on the variable which is furthest away from 0 or 1.

Are you trying to say that you have another objective on the binary variables, which you haven't told the solver, such as if there exist many solutions, you want the solution which minimizes the index to the nonzero element

Supply data also, when you supply code

[Jason]

Thank you, Johan. I think you opinion is suggestive. 

For example, in the current code, the result of SumofSet1 and SumofSet2 is following.Thus I want the 6th number of z1 equal to 1, all others equal to zero; 11th number of z2 equal to zero, all other number of z2 equal to 0. But the current result all gives the last number of z1 and z2 equal to 1, which are not I wanted. Besides, this make me confused about inherent mechanism of branch and bound method.



 Following is my code and the initial data:

在此输入代码...
S=256;
A=4;
n=15;

limpr=sdpvar(S*A,1);
z1=binvar(n+1,1);
z2=binvar(n+1,1);       
F=[Aeq*limpr==beq,limpr>=0,sum(z1)==1,sum(z2)==1];
lpmat=reshape(sum(reshape(limpr,A,S)),n+1,[]);
SumofSet1=transpose(fliplr(cumsum(fliplr(sum(lpmat)))));
SumofSet1(1)=[];
SumofSet1(end+1)=0;
         
SumofSet2=flipud(cumsum(flipud(sum(lpmat,2))));
SumofSet2(1)=[];
SumofSet2(end+1)=0;
         
F=[F,SumofSet1<=ones(n+1,1)-z1+1e-8,SumofSet2<=ones(n+1,1)-z2+1e-8];
obj=f'*limpr;

ops=sdpsettings('solver','bnb','bnb.branchrule','first','bnb.method','depth','bnb.solver','linprog');
optimize(F,obj,ops);
delta=value(obj);

[Johan Löfberg]

Your code says that at least one of the elements in SumofSet1 should be less than 1e-8, and at least one of the elements in SumofSet2 should be less than 1e-8. Looking at your solution, it clearly satisfies this

>> value(SumofSet1)

ans =

    0.9302

    0.8188

    0.6242

    0.4165

    0.2088

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

    0.0000

         0

Looking at z1 indicates that the element it has explicitly forced to be less than 1e-8 is the last element. Many other elements are effectively zero though, so the solution is not unique, z1 could have had a 1 in any element, except the first 5

[Jason]

Yes. But do you know is there any other methods we could set the corresponding indice of first zero value of SumofSet1 of z1 to one,  or when we find the first zero of SumofSet1, if there a method we could ignore the constraints afterwards, because they will be all redundant.

[Johan Löfberg]

hence, since the solution isn't unique, you have to either

1. Add a term to the objective, which tells the solver how you judge different solution. For instance, if you want the z1 with lowest index, add smallnumber*(1:length(z1))*z1. This might tweak the solution though as you are usin a different objective and it is not sure that this new objective will lead the solver to select among the previously optimal set.

2. Solve the problem, and the resolve the problem with a new constrant that the objective must be at most the objective that you just found, and use the objective (1:length(z1))*z1

[Jason]

Thank you ! Yes, I think the second method is more proper.  since we have already gotten the value of SumofSet1 and SumofSet2, it would be easy to get z1,z2.  But, still I am still a little confused about where branch and bound have been used.   Because computation time is a important indicator to me and this formulation could be solved by bnb, CPLEX, even we can use linprog function. do you think bnb is much faster than other solvers?

[Jason]

[Johan Löfberg]

so it would be

optimize(F,obj,ops);

optimize([F,obj<=value(obj)],(1:n+1)*z1+(1:n+1)*z2,ops);

branch-and-bound is used in both calls, but since the problem is trivial, it doesn't have to branch anything when it solves that problem. you could just as well have solved the first problem with z1 and z2 as continuous variables, and the solution would have been integer. The second problem reuqires some branching.

[Johan Löfberg]

No, I definitely do not think bnb is much faster than other solver. On the contrary, bnb is the absolutely slowest solver you can use in YALMIP for MILPs. You never use it for MILPs/MIQPs or MISOCPs, since there are much better alternatives for those problem classes

[Jason]

Thank you very much, Johan !  Behind tthis mixted-integer LP formulation, every time it seems choosing the last number of z1 and z2 for branching, which results in the formulation is trivial. But, I have seen many papers using this MILP formulation instead of LP for a heuristic policy reason or a computational time reason. If the formulation is indeed trivial, do you think is there still exists any point  they are insisting in this MILP?

[Johan Löfberg]

I don't know from where you have the claim that it chooses the last variable for branching. When it solves the original problem here, it never branches, so the statement makes no sense.

You have only seen that the LP happens leads to a binary solution, for this particular instance, and some specific LP solver. There might be instances where a MILP approach is necessary, i.e., where you are not as lucky