Originally posted by: alnaggar.aliaa

Hi, 

I'm implementing Benders algorithm "manually", not with the new built-in feature in Cplex as I want to eventually add additional cuts. When I pass the cuts generated from the subproblems to the master problem as lazy constraints, the algorithm terminates after a while but gives a solution that is actually not optimal to the original problem. When I try implementing the algorithm without lazy constraints, i.e solving the master problem from scratch at every iteration, it does not really converge after a reasonable amount of time (4 hours or so) and the gap between the LB and UB is actually big too. I don't understand the behavior of the lazy constraints. Why does the problem terminate without the condition being satisfied? Also, I noticed that if I look closely at my code, when using lazy constraints for given iteration the objective function value and the values of the variables of the master problem are different than resolving the problem at every iteration. How is this possible? Thanks.

I'm going to assume "not optimal" means feasible but suboptimal. Is the solution suboptimal by more than the termination criteria (absolute and relative MIP gap parameters) should allow? If so, the most likely explanation is a defective cut generator. Assuming you know an optimal solution, try plugging it into each lazy constraint generated (before adding the constraint to the model) and see if one of your lazy constraints rejects the solution. (If you don't know an optimal solution, how do you know the solution you are getting is suboptimal?)

As to the difference between lazy constraints (the "one tree" approach) and fully solving the master after each Benders cut is added, you are generating significantly different search trees in one method versus the other, so there is no reason to expect to see, for example, the same objective values after the same number of iterations in one versus the other.

Originally posted by: alnaggar.aliaa

Thanks a lot for your answer.

Actually I'm suspecting that it is a problem in my implementation, though I'm unable to tell where the error is. I'm using Python and it seems that the callback function stops on its own at a certain point even when the set condition I have is unsatisfied. This could be due to the fact that my problem seems to send a lot of redundant cuts, so I'm thinking maybe after a few iterations the callback function decides that this is the optimal solution since I'm not sending cuts that affect the feasible region? 

What I meant by a suboptimal solution is that the algorithm terminates even though the surrogate is lower than the subproblem objective function value. I'm not sure if redundancy is a factor, but if I loop instead of using the callback function, I go through many more iterations and the gap does eventually get closer. 

Thanks again. Any insight would be really appreciated. 

If by redundant cuts you mean the same cuts over and over, that should not happen, assuming you are adding the cuts globally and not locally. If you are adding cuts locally, cuts can repeat (in different parts of the search tree), but that would not affect the validity of the algorithm.

When your lazy constraint callback returns a cut, that cut should be violated (by an amount greater than the feasibility tolerance) by the candidate solution that was fed to the callback. I suggest "hacking" your callback so that you can send it the suboptimal final solution, and then stepping through the code in a debugger to see why it fails to generate a cut that makes the suboptimal solution infeasible.

Originally posted by: alnaggar.aliaa

Thank you very much for your help. I found a bug in my code and now it is running with no problem. Thanks again.