How can Benders decomposition be faster then Gurobi?
AnsweredHi
I'm Kai, a graduate student.
I recently worked on Benders decomposition to solve MILP (master problem is MILP, subproblem is LP) and read some papers. They always declare that Benders decomposition can be faster than solvers (Gurobi or others) with their improved method. However, I tried to use callback, pareto-optimality cut，something like them to improve the classic Benders decomposition. Although the code works and can provide optimal solution, it takes much more time than Gurobi. (P.S., Gurobi is so good.)
So, my question is if you guys have some experience that your own coding Benders can be faster than Gurobi. If so, how you improve in the Benders algorithm.
Thank you in advance and so appreciated if you can share your experience.
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Kai,
Not all models might profit from using Benders decomposition. When applying Benders decomposition, you project out parts of the model and dynamically re-add this information in terms of feasibility and optimality cuts within a branch-and-cut scheme. So, you start with a smaller master model but if you have to add a lot of Benders cuts throughout the branch-and-bound algorithm, it might have been better to hand over the complete model to the solver from the beginning. In the latter case, the solver exploits the information from the complete model within presolving, cutting, heuristics, branching, etc., while in the Benders case, the solver does not have that much information in the beginning.
On the other hand, if only small parts of a model are relevant to find an optimal solution, Benders decomposition can lead to significant performance improvements. But this usually involves some tuning of the Benders branch-and-cut algorithm. You have to decide how many and which Benders cuts to add when you find multiple cuts in your LP subproblem. This is not a trivial procedure. When you investigate the Benders literature, you will see that people apply a lot of (problem-specific) tricks that lead to the best results.
To summarize, it is not easy to recommend specific techniques without knowing the problem definition, the instances, and the implementation details.
Best regards,
Mario1 -
-
Dear Dr. Ruthmair
Thanks a lot for the detailed explanation.
The problem is indeed that I add a lot of bender cuts to the smaller master problem. I think it is important to choose the benders cuts. Too many cuts seem to cause the difficulty in solving the MILP master problem. Maybe I should try to find some methods to deal with the cuts.
Thank you anyway.
Best regards,
Kai
0 -
-
Dear Ruthmair,
Recently, I also try to use benders decomposition to solve a large-scale problem, and I find that with the increasing of iterations, there are more and more feasibility and optimality cuts are added to the master problem, which leads to the master problem being solved slower and slower. In other words, more cuts lead to an increase in the computation time of master problem. Could you give me some advice to improve this?
In addition, in my problem, the solving process of the master problem is time-consuming while the subproblem can be solved quickly. For this type of the problem, could you have some good idea to handle and improve it?
0 -
-
-
Usually, you need to do some cut management in such situations. This means you should not add all violated cuts found in the subproblems. You could differentiate and decide for each cut based on:
- how much a cut is violated, e.g., absolute value between left- and right-hand side
- the number of cuts already added in this iteration (you could define an upper limit)
- the structure of already added cuts in this iteration, e.g., it could make sense to add more diverse cuts concerning the variables involved.
You might come up with many more ideas on how to evaluate the "value" of a cut before adding it.
0 -
-
Many thanks for your valuable suggestions! Dr. Ruthmair
0 -
Post is closed for comments.
Comments
6 comments