• 1 reply
  • Latest Post - ‏2013-08-01T13:53:55Z by Falcon_G
1 Post

Pinned topic Bender's decomposition

‏2013-07-14T19:52:34Z |

(Apologies for crossposting I posted this first in the CPLEX folder but later realized there is a specialized subforum for Math Programming)

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?



  • Falcon_G
    1 Post

    Re: Bender's decomposition


    What folows is my personal experiences:

    1. in a MIP with general integer variables and not necessarily binary vars, with network substructures, usually benders approach, as far as I have experienes and those problems that I have tried, is not an effocoent approach.

    2. A text-book implementation of benders (even all the others too) is not usually the most efficient one. You always have to tweek it before it can be very efficient. an example such cases is usually the network design models with flow subproblem. it was known from very early years and many people proposed several ways such as finding relative interior etc