Applying LR to the B&B for MIPs
Answered
Hi everyone
I am trying to apply Lagrangian Relaxation to Branch-and-Bound to solve a MIP problem. How can I use LR during branching? I know that I have to use callbacks but I do not know how I can tighten the relaxed model at each node by using LR.
Regards
Sajjad
-
Hi Sajjad,
Unfortunately, you cannot modify the model in callbacks during optimization. The algorithm requires that the initial model is complete. Otherwise, it would not be correct. There is the possibility to add further constraints and explicitly state that the initial model was not complete (via LazyConstraints), but you cannot modify existing constraints.
Using LR as node relaxation in a branch-and-bound can be an efficient (problem-specific) approach. In this case, it might even make sense to implement your own branch-and-bound.
If this does not help, how exactly do you want to involve LR in the MIP solution process?
Best regards,
Mario1 -
Hi Mario,
Thank you for the information.
According to your answer, two questions are possible:
1- If I implement my own branch-and-bound algorithm via gurobipy, I will need to use the LP model and Gurobi as a solver and then get the solutions to apply branch-and-bound at each node? If so, is it possible to do it by your features in gurobi like the MIPNODE method in the callback function?
2- Actually, the LR as a relaxation approach gives me some integer solution at each iteration, but these solutions in most cases are not feasible for the original problem since I relax some constraints. Therefore, it seems that using the LR helps me to have a tighter bound as an initial point to apply B&B which is hopefully close to the optimal solution. So, if I get a lower bound for my current MIP problem and its related solution, then how I can continue the optimization by applying the B&B?
To be more clear, we can imagine the GAP as a well-known MIP problem to which the LR has been successfully applied. If we relax the inequality constraints set, then how gurobi can help us to get to an optimal or near-to-optimal solution? In fact, after some iteration, we get a lower bound which is infeasible for the original problem. In the internal loop of the LR, as we solve subproblems, we can use gurobi as a solver. How can we use the LR results to get an optimal solution by using gurobi?
Regards,
Sajjad
1 -
- With implementing your own branch-and-bound, you would not use Gurobi at all or use Gurobi only to solve node LP relaxations. You would do your own branching, etc. If you want to use Gurobi's branch-and-bound, you can only do what is allowed in callbacks, e.g., add additional cuts or inject feasible solutions in MIPNODE or MIPSOL callbacks. Only replacing Gurobi's LP solver with an LR approach and keeping everything else is unfortunately not possible.
- If the LR bound is better than the LP bound and can be computed faster, then it is probably better to build a standalone tailored approach without anything else, independent of any solver. Usually, you might even have dedicated branching rules in such cases.
0 -
Thank you again for your explanation.
Now, I wonder if you could help me with the following strategy:
- Imagine we get a lower bound and an infeasible solution that is integral obtained from an independent LR algorithm. Now, Can I set the initial relaxation points in the B&B in these solutions? In other words, can I give gurobi a set of initial integer solutions, which are infeasible, to start the branch-and-bound in?
Regards
Sajjad
0 -
Handing over multiple infeasible (or partial) solutions to the solver via MIP starts is possible. The solver then tries to repair (or complete) the solutions, but there is no guarantee that this works out. Even if some feasible solutions are obtained, their objective values can be pretty bad. Still, it could be worth a try.
Intuitively, one might think it is a good idea to hand over a dual bound to the solver via some constraint "objective function >= dual bound" (for minimization problems). Still, even if this dual bound is better than the root relaxation bound from the solver, this could worsen performance, see this article.
0 -
I think that I got my answer regarding the B&B. Thank you!
What if we have a heuristic and we want to use its solution for our next optimization step by Gurobi? Like two-stage programming strategies with a Huristic as a solver for the first stage and Gurobi as a solver for the second. Is it the same as before as you suggested MIP start?
Regards
Sajjad
0 -
Yes, exactly. If the variable names are the same, you can use MIP starts to hand over an initial solution.
0 -
Thanks, Mario!
0
Please sign in to leave a comment.
Comments
8 comments