Originally posted by: rezir

I am implementing Bender's method using CPLEX example for ATSP. I have to add an optimality cut in my problem. Stopping criteria for adding optimality cut is 1) master problem (MIP) has an optimal solution and  2) the objective value of the sub problem becomes greater (or equal) than a surrogate variable added to the master problem.

I use LAZYCONSTRAINTCALLBACK from "bendersatsp.py". Given that, do I need to check both stopping criteria or the second one is already covered by callback function?

When I add the second termination condition, the problem is solved only for one iteration (one cut). When I do not add this condition, for some instances it finds optimal solution but for others the solution is not optimum.

I really appreciate your help.

The phrase "[s]topping criteria for adding optimality cut" is quite confusing. If the master problem has a (proven) optimal solution, that is indeed grounds for stopping, and CPLEX will stop the search. If an integer feasible solution produces an objective value in the subproblem greater than or equal to the surrogate variable (I assume you are minimizing in the master), that is grounds for producing an optimality cut. It is most certainly NOT grounds for stopping. Inserting a stop under those conditions in the subproblem would definitely explain getting just one cut, and would almost always be incorrect.

Originally posted by: rezir

Thank you so much Dr. Rubin for your reply!

Actually, I looked at the callback algorithm in your blog (Bender's algorithm). I though (c^'_{2}y>z) and (y optimal) in your example both are termination condition for the algorithm. That was wrong!

I'm glad you were able to sort it out.
 

Originally posted by: rezir

May I ask another question, please?

You also indicated something that I am not sure I understand it correctly. Please correct me if I am wrong:

" if the problem has multiple optimal solutions, the optimality cut might has poor performance."

I really appreciate your help!

I'm not sure what the context of that statement was (if, in fact, I made it). I did not say it in this thread, nor in the blog post you cited.

Originally posted by: rezir

Thank you Dr Rubin!

I have a question maybe you have answered, if so please lead me.

The benders that I have incorporated for a minimization problem has some problems: 1) it does not converge in some instances; its objective function is less than that of the CPLEX and the solution for decision variables are different. 2) it is much slower than the CPLEX.

Please take a look at the following results that I got for an instance and let me know how I can improve the benders.

if I solve it by CPLEX directly:

    Solution status: 101

    Objective function value: 60352.2

    gap: 0.0

    u= [300.0, 200.0]     #decision variable value

    time: 0.32222890853881836

If I solve it by BD:

    Solution status: 102

    Objective value: 59273.43999999999

    gap: 0.007941757027847982

    u = [362.0, 378.0]    

    time: 35.84594488143921

The solution codes and gap values indicate that the direct approach (CPLEX) reached optimality (0 gap) while the Benders decomposition stopped because it was acceptably close to optimal, as dictated by the absolute and relative gap parameters. Assuming the gap you printed is the relative gap (approximately 0.8% for the Benders run), the upper bound for the Benders run at termination must have been approximately 1.008*59273.33, which is well below the CPLEX objective value. So my best guess is that you generated one or more incorrect Benders cuts.

As far as speed goes, that could be a result of the apparent error in your cut generator, it could be a function of problem size (direct solution could be smaller on small instances, Benders on larger instances), or it could just be that your problem is not well suited for Benders.

Originally posted by: rezir

Hello Dr. Rubin,

Thank you so much for your reply!

In case that Benders cut is incorrect, how I can check that?

To generate the cut I used the following book (chapter 5, L-shaped method, example 1). I just changed the sign of the \theta and direction of the cut. Otherwise the Benders stopped with zero solution. Do you know any reference that I can use to check Benders cut, please?

Birge J.R., Louveaux F. (2011) Two-Stage Recourse Problems. In: Introduction to Stochastic Programming. Springer Series in Operations Research and Financial Engineering. Springer, New York, NY

Take the optimal solution found by CPLEX without Benders and substitute it into each Benders cut you generate. When a cut is violated by that solution, the cut is incorrect. Then you need to figure out, based on the logic you used to generate the cut, why it is incorrect.