Increasing Solving Time in Subsequent Nodes During Strong Branching with Branch and Price
AnsweredHello Gurobi Community,
I'm working on a problem using branch-and-price with strong branching. In this method, I make new nodes for each special fractional variable in the solution. I solve the RMP for each candidate node by setting the chosen variable to 1.
I noticed that when I do this, my model becomes simpler because many variables conflict with the one set to 1, so I set them to zero (setting their upper bound to zero). However, when I move to the next node, I have to reset these variables and then fix new ones to zero.
The problem is, the first node I solve is really quick, but the next ones take much longer. I'm not sure why it's happening. Is it because of how the solver works or something to do with changing the model each time?
Any advice or tips would be very helpful.
Thank you.
-
Hi Tifaout,
What exactly takes longer? Is it only the time to solve the LP relaxation that takes longer, or does it take a longer time to modify the model from one node to the next?
Have you tried to only modify the bounds of the branching variables, and leave the rest of the preprocessing (setting other variable bounds to zero) to the solver? It could be that this is more efficient.
Best regards,
Mario0 -
Hi Mario,
I greatly appreciate your response!
I've noticed that the most time-consuming part is solving the LP relaxation. Your advice was incredibly valuable. Specifically, I realized that adding the constraint "variable to branch on equals 1" (x = 1) directly into the model, rather than adjusting its lower and upper bounds to 1, significantly increases the model's complexity. This approach leads to a rapid increase in the number of variables, particularly as I'm employing a branch and price strategy. Hence, I observed the unusual behavior I initially mentioned.
Based on this insight, I plan to modify and fine-tune my experiments. I aim to identify the most effective strategy for strong branching, particularly in evaluating candidate nodes. I'll consider using variable fixing to zero or allowing the preprocessing to handle it.
Your guidance has been incredibly helpful, Mario. Thank you once again!
Kind regards,
Tifaout
0
Please sign in to leave a comment.
Comments
2 comments