Benders decomposition (L-shaped) with cbLazy in MIPSOL callback: how to avoid losing presolve reductions from LazyConstraints=1?

Answered

Abhishrut Sinha

October 27, 2026 11:19

• 
• 

I’m solving a two-stage stochastic MIP with a multi-cut L-shaped method (Benders decomposition). The problem has complete recourse, so I only add optimality cuts, and the second-stage optimal duals have a closed form, so generating cuts is cheap. The master problem has binary first-stage variables and one θ variable per scenario (500 scenarios). To strengthen the master problem before branching, I first solve its LP relaxation for 10 iterations, adding the optimality cuts violated at each fractional solution as ordinary constraints. I don’t add cuts at fractional nodes during branch-and-bound.

In my single branch-and-bound tree implementation, I then restore integrality. Whenever an integer-feasible solution is found in the tree, I evaluate its second-stage cost in a MIPSOL callback and add the violated optimality cuts with cbLazy. This requires setting Params.LazyConstraints = 1, which I understand disables some presolve reductions. Performance is poor: optimality gaps are around 90% when the 3600-second time limit is reached.

As a test, I also solved the extensive form (no decomposition, no callback) with LazyConstraints = 1. It stalled compared with the same model solved with LazyConstraints = 0, which suggests the parameter itself is costly for my model.

My questions:

• Is there a way to keep these reductions while still adding Benders optimality cuts with cbLazy in a MIPSOL callback? For example, a combination of parameters, or a way to tell Gurobi that the lazy constraints only involve certain first-stage variables?
• If not, what is the recommended way to implement single-tree Benders decomposition in Gurobi?

Environment: Gurobi 11.0.2, Python API. The master problem has about 17,000 rows, 16,000 columns and 15,000 binary variables before cuts are added.

Thank you!

Related to

• Bender's

0

• 

  Riley Clement

  • Gurobi Staff

  October 28, 2026 00:10

  Hi Abhishrut,

  Is there a way to keep these reductions while still adding Benders optimality cuts with cbLazy in a MIPSOL callback?

  Unfortunately not.  When LazyConstraints=1 we must turn off dual reductions.  You could confirm these are responsible for the performance by repeating your experiment with the extensive form, but setting DualReductions=0 instead of LazyConstraints=0.  Dual reductions will happily remove feasible solutions from the solution space while guaranteeing at least one optimal solution will remain.  When lazy constraints are added via a callback then there is no way that the guarantee is valid.  After applying dual reductions perhaps the only solutions remaining will be removed by the lazy constraints.

  If not, what is the recommended way to implement single-tree Benders decomposition in Gurobi?

  I think you have the main building blocks in place.  Unfortunately a standard Benders implementation just typically doesn't work that well without various problem specific improvements to the algorithms.  Of course there are other reasons for applying Benders, other than performance.  If you're interested in diving deeper into what sort of enhancements are required for performance then I recommend this talk from "Bender's Day" by Stephen Maher: https://youtu.be/vVuNsx1bfLA?si=lOUM6IY5HlFqYPbH

  - Riley

  0
• 

  Abhishrut Sinha

  October 30, 2026 22:03

  • 
  • 

  Thank you, Riley!

  0

Please sign in to leave a comment.