Originally posted by: LuisdelaTorre

I'm looking for some advice on Benders decomposition.

I've implemented Benders decomposition within a single branch and bound tree using cut callbacks, as described in http://orinanobworld.blogspot.com/2011/10/benders-decomposition-then-and-now.html. My master problem has binary variables, and I want to add trust regions to the master problem. An example of this is found in "A stochastic programming approach for
supply chain network design under uncertainty" - the first equation on page 10 is such a trust region on binary variables y: http://www.optimization-online.org/DB_FILE/2003/06/670.pdf

I have implemented the 'black box' version of Benders decomposition with these trust regions (re-solving a MIP at each iteration shown here: https://docs.google.com/file/d/0B-BSG5eMtXyJZTc1Y2JmZmMtNzIzOS00YmJiLWI3NTUtNDkxZDQxOWFkZmIz/edit), but I'm not sure how to proceed on using the trust regions within a single branch and bound tree.

When I re-solve a separate MIP at each master problem iteration, I can solve without previous trust regions, or remove them all together (I need to solve the master problem without trust regions to update my lower bound), and I'm not sure how I can remove trust regions within the branch and bound tree. I could use branch callbacks and branch on the trust region constraint. This would actually be local branching and not exactly what I had in mind (but it may work well, I don't know).

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think you can implement the trust regions while using callbacks, but you will need to take over the branching process with a branch callback and the node selection process (I think that's a node callback, but it's been ages since I messed with one). The branching strategy works as follows. At any node where you are neither adding nor deleting trust region constraints, let CPLEX branch as it normally would. If you are adding trust constraints, create two children, the left one with the trust constraints and the right one without (so that the right one is a clone of the parent). If you need to delete an old trust region before adding a new one, backtrack to the first unseparated node without the trust region you are deleting, and separate that (left child with new region, right child without).

The node callback determines the order in which nodes are processed. When you add a trust region, it should process the left child next. When you backtrack, it needs to figure out how far.

Benders cuts continue to be added in a lazy constraint callback. Whether they are global or local (contingent on a particular trust region) is something you will need to sort out.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LuisdelaTorre

Thank you as always! This looks like a good way to go.
#CPLEXOptimizers
#DecisionOptimization