Skip to main content

How can Benders decomposition be faster then Gurobi?

Answered

Comments

5 comments

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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,
    Mario

    1
  • Kai Zhang
    Gurobi-versary
    First Comment
    First Question

    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
  • Simin Chai
    First Comment

    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
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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
  • Simin Chai
    First Comment

    Many thanks for your valuable suggestions! Dr. Ruthmair

    0

Please sign in to leave a comment.