Implementing Benders Decomposition with Callbacks

[Lindsay Sanneman]

I have recently implemented Benders Decomposition on a MILP model I created in Gurobi. With Benders, looking at a few test cases, the model is taking longer to converge than with the original formulation.  I am hoping to add in callabcks (Gurobi's lazyConstraints callback)  to speed things up. I have been searching for tutorials on how to do this, but so far have not found much information.  Does anyone know of a source that could provide a tutorial or other information about use of Gurobi callbacks with Benders (particularly with Java would be very helpful)?  I am using Java version 8 with Gurobi 6.5. Thanks so much!

Lindsay

[Tobias Achterberg]

From Gurobi's perspective, a Bender's decomposition is not different from any
cutting plane algorithm. Hence, you may want to take a look at the TSP example

http://www.gurobi.com/documentation/7.0/examples/tsp_java.html

which is also using lazy constraints. In the TSP example, lazy constraints are
only added to cut off integer solutions (you see that the example checks for
"where == GRB.CB_MIPSOL"). If you like, you can also produce lazy constraints or
user cuts to cut off fractional solutions, but I guess for your Bender's
application, producing Bender's cuts only on integer solutions is what you want.

Hope this helps,

Tobias

[Lindsay Sanneman]

Thanks so much! This was very helpful in getting me started.  I have written some baseline code for Benders with callbacks, and I've noticed that when I run the code, each of the cuts added is a feasibility cut and no optimality cuts are added before the problem is solved.  This causes there to be no constraint on the z term (subproblem contribution to the objective in the master problem) and consequently, the optimization is solved incorrectly.  I have a few questions about this:

1) It seems that the problem is solved before all necessary cuts are added.  Is there a way to deal with this or is there information I'm missing in my implementation?

2) What is the convergence criteria when solving a MILP using Benders with callbacks? With nominal Benders, we check if the UB and LB match. But here, I am simply running the master problem with callbacks and adding a cut each time a solution at a node is found.  If the master problem is solved before we have matched master and subproblem objectives, the optimization is solved incorrectly. What can we do about this?

Thanks again!