Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
  • 1.  Benders' Decomposition problem

    Posted 08/14/15 01:34 AM

    Originally posted by: Amir Ghahari


    Hello

     

    I have developed a benders decomposition problem via JAVA. right now it works properly for small instances but once we run a large instance (the instance is solved by CPLEX in 15 minutes optimally) it takes for ever to solve it. In some instances it reach more than 1500 iterations. I am not sure that the complexity of the problem cause this or I have a problem in my code. The only thing that concerns me the most is some times after applying a cut we obtain a better objective function value in master problem which should not be the case. Can someone give some hints that where I should look?


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Benders' Decomposition problem

    Posted 08/14/15 03:24 PM

    Are you solving this the "traditional" way (fully optimize the master, solve the subproblem, add a cut to the master and fully optimize again), or are you using a lazy constraint callback? If the latter, seeing an improved incumbent after adding a Benders cut is common behavior.


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Benders' Decomposition problem

    Posted 08/15/15 10:09 PM

    Originally posted by: Amir Ghahari


    Yes I am solving it in the traditional way. I have used lazy constraint callback as well as I am adding the cut to the model manually. Could you mind explaining more why it is common behavior? Each cut will restrict the feasible region more than before so in the best case scenario we will end up with the same region which will have same objective function. In other scenarios, we cut the optimal extreme point out so it will become worse.. it is a little confusing for me.

     

    Thank you very much


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: Benders' Decomposition problem

    Posted 08/16/15 11:06 AM

    If you use the traditional approach (no lazy constraint) and solve the master to optimality each time (no time or iteration limits), then the objective value of the master solutions should be monotonically non-improving. Any improvement in the final master solution relative to the previous final master solution would indicate a problem with your code (or, possibly, a numerically unstable model).

    If you terminate the master solutions early (time or iteration limit), then you are apply cuts based on possibly suboptimal solutions, so the master objective can improve (by moving from a suboptimal to an optimal solution) or get worse (cutting off what was a superoptimal solution).

    If you use a lazy constraint callback, the second case applies: some of the solutions triggering the callback may be suboptimal, others may be superoptimal, so the objective can change in either direction.

    Using the traditional approach, you can add the new cuts to the master problem as lazy constraints, but that is not the same as using a lazy constraint callback. Lazy constraint callbacks are incompatible with the traditional approach.


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: Benders' Decomposition problem

    Posted 08/20/15 10:54 PM

    Originally posted by: Amir Ghahari


    Thank you very much for your help


    #CPLEXOptimizers
    #DecisionOptimization