Cuts in Benders

Answered

Saeed Abdolmaleki

May 04, 2025 23:18

• 
• 
• 

Hello Gurobi Team,

While analyzing the solver logs during the application of Benders decomposition using both the callback-based and classical (cutting plane) methods, I noticed that the number of cuts generated via the callback approach is almost twice as many as those generated through the classical method.

Could you please explain why this discrepancy occurs?

Best

Saeed

Related to

• Bender's
• User Cuts

0

• 

  Riley Clement

  • Gurobi Staff

  May 05, 2025 01:11

  Hi Saeed,

  I think it is worth mentioning that you could run either the callback approach, or the classic approach twice, and change the Seed parameter between them, and you would find a different number of cuts added for the same approach (at least for non-trivial models).  This is because master and subproblems may have multiple optimal solutions (which give different cuts), and for each optimal solutions there are many solution paths.

  If you were under the impression that using Bender's decomposition on a model would result in a unique set of cuts required, then know this is not true.

  The biggest difference though is that these frameworks are doing different things.  In the classic iterative approach we solve the master to optimality - there may be many suboptimal solutions found along the way, but we only add a cut when we get to the optimal solution.  In the simplest implementation of a callback approach we would have added a cut each time we found these suboptimal solutions.  You might ask “do we have to add a cut if they are suboptimal”, but at the time of discovery we do not know whether they are suboptimal or not - until we find better solutions, or improve the dual bound so that it equals the objective value for that solution, there is no way of knowing.

  - Riley

  0

Please sign in to leave a comment.