Originally posted by: alnaggar.aliaa

Hi, 

I'm trying to implement Benders decomposition using Python API. I have previously done several implementations using MATLAB, but because the lazy constraint callback class is not available for MATLAB, my code was very inefficient. 

Looking at the example provided by Cplex (bendersatsp.py), I don't find it very straight forward. Though I found some explanations of the code in other threads and elsewhere, I don't see where the algorithm iterates. In my previous implementation, I would have a while loop that solves the Master Problem and Subproblem until a specified stopping criteria is reached or a certain tolerance. I thought the implementation should be similar, but instead of solving the MP from scratch, you pass the cuts obtained from the subproblem as lazy constraints, but you do iterate. I would really appreciate your input. Thank you very much.

Implementing Benders decomposition with lazy constraints does not require explicit iteration. The master problem is solved as a MIP via tree search. Whenever tree search finds an integer feasible solution the lazy constraint callback is invoked. In this callback you can separate feasibility or optimality cuts and return them. This is the point at which in an iterative scheme you would start a new iteration. In the approach using lazy constraints CPLEX instead adds the separated cuts to the problem and continues the tree search, it does not start from scratch.

Originally posted by: alnaggar.aliaa

Thanks a lot for the informative reply. It makes sense now.