Hello author

[yoyo0210]

Firstly, Does the callback technique used in the bendersClassicWithCallBackLazy.py document mean the same as the traditional Branch and Benders cut?
Secondly, your Bedders code is the best I've ever seen, thank you for graciously sharing it.

[prameshk]

bendersClassicWithCallBackLazy.py maintains a single tree and apply Benders cut as part of their branch-and-cut. Both are same technically, but bendersClassicWithCallBackLazy.py is supposed to be faster as we are not solving the master MILP again and again. Thanks for using the code. The implementation in the current code can be further improved.

[yoyo0210]

Thank you, author, for your selfless answer yesterday! I still have some questions.
About the bendersDisaggregatedCuts.py document, the README says: these methods computes the solution in lower computational time than the Gurobi solver for this problem.

• Question 1: But whether I run bendersDisaggregatedCuts directly or add it to my own benders, it is not as fast as gurobi directly, which is inconsistent with what the README file says.

• Question 2: And Benders with disaggregated cuts and callbacks solve slower than Benders with disaggregated cuts, the former is obviously a fusion of two acceleration strategies, and it stands to reason that it should be faster, which is what I don't understand.

I would appreciate it if you could take the time to answer my questions.

[prameshk]

Hi,

Question 1: But whether I run bendersDisaggregatedCuts directly or add it to my own benders, it is not as fast as gurobi directly, which is inconsistent with what the README file says.
Answer 1: Gurobi has significantly improved their solver since this code was uploaded. Who knows if they have implemented better computational techniques than bendersDisaggregatedCuts in their solver. For some instances, the current code may work faster.

Question 2: And Benders with disaggregated cuts and callbacks solve slower than Benders with disaggregated cuts, the former is obviously a fusion of two acceleration strategies, and it stands to reason that it should be faster, which is what I don't understand.
Answer 2: Again, there is no surety that any strategy which seems faster in theory would be actually fast in practice. This depends on instance, programming skills, data structures used, how is it interacting with gurobi, etc.

Overall, these are the techniques worth trying for this problem.

[yoyo0210]

Hello author, I'm going to trouble you again. I don't understand what the new variable xi of paretoSubProblem is for. I really want to figure it out and look forward to your generous answers, thank you so much!

[prameshk]

Pareto cuts can be useful in cases when there is degeneracy in the subproblem. After solving the subproblem, you solve another ParetoSubproblem to possibly get a better cut than the original subproblem. In above picture, I am trying to solve the dual of the ParetoSubproblem and xi represent the dual variable corresponding to the constraint where objective value of ParetoSubproblem is constrained to be equal to the subproblem objective value. To get a better clarity, please read the original paper on Pareto Benders cut:

Magnanti, Thomas L., and Richard T. Wong. "Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria." Operations research 29.3 (1981): 464-484.

[yoyo0210]

Teacher author, I'm bothering you again

• When solving my problem with the above benders code, the LB will end up being larger than UB (minimization problem), I would like to know if you will have this situation? What is the general cause of this situation?

• When solving the large-scale problem with callback+disaggregated cut, the resulting ub and lb are much different, the algorithm stops, and the problem that LB is larger than UB also appears.

• If I want to highlight the superiority of the Benders algorithm, wouldn't it be better to replace the solver with cplex?

Thank you for your selfless reply again！

[prameshk]

Hi,

Q. When solving my problem with the above benders code, the LB will end up being larger than UB (minimization problem), I would like to know if you will have this situation? What is the general cause of this situation?

A. There can be two reasons for this. Either there are some numerical issues due to which the solver rejected a cut or there is issue with the code. Please check if everything is alright with code and the model data is scaled properly.

Q. When solving the large-scale problem with callback+disaggregated cut, the resulting ub and lb are much different, the algorithm stops, and the problem that LB is larger than UB also appears.

A. Same issues are possible. Manually testing the numerical errors might help.

Q. If I want to highlight the superiority of the Benders algorithm, wouldn't it be better to replace the solver with cplex?
A. CPLEX has a benders functionality while Gurobi doesn't. In most cases, Gurobi/solver will be better than the classic Benders. The difference may come if you implement it differently with new cuts.