Originally posted by: srvh

At the given node, when one of the right or left branch is infeasible how to compute strong branching score? for example, strong branching score is 2*max{(q-)=200,(q+)=infeasible} +min{(q-)=200,(q+)=infeasible}. At this formula what is min between 200 and infeasible and what is max between 200 and infeasible?At the given node, when one of the right or left branch is infeasible how to compute strong branching score? for example, strong branching score is 2*max{(q-)=200,(q+)=infeasible} +min{(q-)=200,(q+)=infeasible}. At this formula what is min between 200 and infeasible and what is max between 200 and infeasible?

Thanks.

Serveh

Originally posted by: AndreaTramontani

Dear Serveh,

I'm not sure I understand why you need to compute strong branching scores for infeasible nodes.
Assume the fractional solution at a node is x*, and assume you try strong branching on variable x_j, i.e., you try the left branch x_j <= floor (x*_j) and the right branch x_j >= ceil (x*_j).
If, for instance, the right branch is infeasible, then you don't need to branch on x_j, and you can simply add the bound constraint x_j <= floor (x*_j) which is globally valid.

Best,
Andrea

Originally posted by: srvh

Thank you very much for your answer, for example at a given node we have 5 fractional variables, I want to compute Strong Branching score for all 5 fractional variables then select maximum score for next branching.

For this reason When one of the variables is infeasible I want to know how compute SB score for that variable.

Originally posted by: AndreaTramontani

Dear Serveh,

I really do not understand why you need a strong-branching score for a branching that is not needed.

Following your example, assume at a node N0 you have 5 fractional variables, x1, ..., x5, with values x1*, ..., x5*.
You do strong branching on them and, for instance, you find out that branching up on x1 and on x2 yields an infeasible node.
On the other hand, for variables x3, x4, x5 you can compute strong branching scores s3, s4, s5.
You know that you don't need to branch on x1 and x2. I.e., the bound changes x1 <= floor (x1*) and x2 <= floor (x2*) are valid for every child node of N0.

So you have two possibilities:

1. You want to branch using the current scores you computed for x3, x4, x5.
Assume s3 > s4 and s3 > s5, so you want to branch on x3.
Then, you create two children nodes N1 and N2.
On N1, you impose the branching conditions x1 <= floor (x1*), x2 <= floor (x2*), x3 <= floor (x3*).
On N2, you impose the branching conditions x1 <= floor (x1*), x2 <= floor (x2*), x3 >= ceil (x3*).
The branching is valid, because you know that x1 >= ceil (x1*) or x2 >= ceil (x2*) lead to an infeasibility.

2. You want first to update the node by imposing x1 <= floor (x1*) and x2 <= floor (x2*), and then (if you still have some fractional variables),
you want to recalculate the strong branching scores.
Then, you create only one child node N1, in which you impose the "fake" branching conditions x1 <= floor (x1*) and x2 <= floor (x2*).
I say "fake" because you are creating only one child node, so you are not really branching but you are instead tightening node N0 as N1.

Both options above can be implemented from within a branching callback, they are both correct, and they do not require to calculate scores for infeasible nodes.

Best,
Andrea

Originally posted by: srvh

Dear Andrea,

Thank you for your reply. You said ''you don't need to branch on x1 and x2 ". Why? I think When I prune one child (from x1 or x2), The calculate on B&B maybe fewer than if I branch first on x3 or x4 or x5. Because I must compute strong branching for fractional variables at node N1 and N2 but if I branch x1 or x2, i just compute strong branching for fractional variables on node N1.

You suggest two possible, but i want to compute all of them in one possible. So, I compute SB for x1, x2, x3, x4 and x5 then each one is maximum I select it for branching. But I don't know how to compute SB for x1 and x2.

Best

Serveh

Serveh, I think you are missing Andrea's point. Lets stick with the example in which strong branching determines that branching up on x1 or x2 is infeasible. At that point you know that x1>=ceil(x1*) and x2>=ceil(x2*) are infeasible. So in any child node you create you will have x1<=floor(x1*) and x2<=floor(x2*). At the current node you don't have to branch on x1 or x2. Instead you branch on one of the other variables (whichever yields the best strong branching score). Assume that strong branching suggests to branch on x3. So you create two child nodes: N1 with x3<=floor(x3*) and N2 with x3>=ceil(x3*). Additionally, you add to both nodes the conditions that you just found for x1 and x2: x1<=floor(x1*) and x2<=floor(x2*). In other words, your branching does not change the bounds of only a single variable. It changes the bounds of three variables.

The point here is that at node N0 you definitely don't want to branch on x1 or x2. Such a branching would be useless since you already know that one of the children is infeasible. So you would create two children, only to immediately prune one of the two. So you don't want to look at x1 or x2 when you look for a variable to branch on. Instead you want to branch on another variable and along with branching on that other variable you add the conditions you found on x1 and x2. Since you don't even consider branching on x1 or x2 in this case, you don't need a strong branching score for them either.

With this strategy you don't lose any information. Instead the newly created nodes have more information (they have bound changes for 3 variables).

Originally posted by: srvh

Okay.

Thank you very much.