Originally posted by: UserCplex

Hi All,

For long Bender's decomposition has been considered to be faster than straightforward solution of an MIP. Does anyone have any reference to recent work that shows that for relatively hard MIPs? I wrote a simple Bender's code for an MIP but straightforward CPLEX solution times were much better than Benders. So, I have my doubts.

Also, is there any plan to include Bender's decomposition as one of the options within CPLEX itself? Would it not be possible in the future to identify MIPs where, for instance, on fixing the IP variables, the rest of the problem becomes a Network Problem (say) and then CPLEX itself can solve the problem via Benders decomposition?

Thanks.

"For long Bender's decomposition has been considered to be faster than straightforward solution of an MIP." This is not true. Bender's is faster than a standard branch-and-cut approach on some MIP problems, but far and away not on all. On some problems where Benders might help with "large" or "difficult" instances, it may be a waste of effort when the instances are "small" or "easy". On some classes of problems, Benders is unlikely to help even when the instances are difficult, because the structure of the problem is better suited to branch-and-cut than to Benders.

As for baking Benders into CPLEX, someone from IBM will have to do that. For what it's worth, I believe that AIMMS (which is a modeling language, not a solver) now contains intrinsic support for Benders.

Paul

Originally posted by: UserCplex

I am actually trying to solve a problem quite similar to Geoffrion and Graves problem of 1974: 

"Multicommodity Distribution System Design by Benders Decomposition" 

The problem is not exactly the same but similar. Once I fix the integer variables, the rest of the problem becomes a "simple" network problem. I am not able to replicate their reported gains over straightforward CPLEX MIP solution methods.

My Benders subproblem (pure IP) seems to be enumerating quite a large number of combinations. Also, the number of Bender's cuts seem to be quite high - nowhere near the "few Bender's cuts are sufficient" claim in the 1974 paper.

Of course, this could be because my coding of Benders is suboptimal. It could also be because MIP solution methods have simply become faster and more sophisticated over time. "Beating CPLEX" may become more and more difficult. That is why I was interested in any recent papers that report gains using Benders over straightforward solution methods.

Solver improvements are likely a major contributing factor. Also, not all Benders cuts are created equal. There's a nice paper by Magnanti and Wang about how to accelerate Benders by generating deeper cuts.

As for success stories, I worked on a model for placing toll booths in which Benders allowed us to solve at least some instances thati were too difficult for CPLEX with basic branch and cut. It was published in 2009 in Operations Research (Bai & Rubin).

Paul

Originally posted by: UserCplex

Thanks. Will look at the references.