Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
1 reply Latest Post - ‏2013-08-01T13:53:55Z by Shahin_Gelareh
UserCplex
UserCplex
1 Post
ACCEPTED ANSWER

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?

 

Thanks.

  • Shahin_Gelareh
    Shahin_Gelareh
    1 Post
    ACCEPTED ANSWER

    Re: Bender's decomposition

    ‏2013-08-01T13:53:55Z  in response to UserCplex

    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