How can Benders decomposition be faster then Gurobi?

Answered

Comments

2 comments

  • Mario Ruthmair

    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
    Comment actions Permalink
  • Kai Zhang

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk