Decision Optimization

 View Only
Expand all | Collapse all

CPLEX Benders Strategy

  • 1.  CPLEX Benders Strategy

    Posted Tue October 05, 2021 09:30 AM
    Edited by System Fri January 20, 2023 04:10 PM
    Hi,

    When we use Benders strategy provided by CPLEX, what exactly happens in the background? Is the problem being solved fully by Benders? or Does CPLEX only use Benders to speed up the B&B process? 

    I use JAVA API and set my strategy as FULL just to see how CPLEX performs when using the Benders decomposition to make a comparison with my own implementation.

    cplex.setParam(IloCplex.Param.Benders.Strategy,
    	                         IloCplex.BendersStrategy.Full);​


    When I look at the log, this is what I see:

    CPXPARAM_TimeLimit                               5400
    CPXPARAM_Benders_Strategy                        3
    Found incumbent of value 0.000000 after 0.00 sec. (1.40 ticks)
    Tried aggregator 1 time.
    MIP Presolve eliminated 908 rows and 0 columns.
    MIP Presolve added 13792 rows and 0 columns.
    MIP Presolve modified 391 coefficients.
    Reduced MIP has 43886 rows, 31000 columns, and 159289 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.17 sec. (55.44 ticks)
    Tried aggregator 1 time.
    MIP Presolve eliminated 14033 rows and 1380 columns.
    MIP Presolve added 14359 rows and 0 columns.
    MIP Presolve modified 479 coefficients.
    Reduced MIP has 44212 rows, 29620 columns, and 159040 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.19 sec. (71.04 ticks)
     
            Nodes                                         Cuts/
       Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
     
          0     0      965.4143                      Benders: 500        0         
          0     0       71.1323                      Benders: 142     3271         
          0     0       65.7413                      Benders: 120     3681         
          0     0       62.9035                       Benders: 72     4341         
          0     0       60.8045                       Benders: 35     4920         
          0     0       59.9468                       Benders: 14     5285         
          0     0       59.6935                       Benders: 16     5490         
          0     0       59.5370                        Benders: 5     5655         
          0     0       59.4217                      Benders: 117     5756         
          0     0       58.3767                       Benders: 35     6285         
          0     0       58.1217                       Benders: 17     6595         
          0     0       58.0198                        Benders: 4     6765         
          0     0       58.0002                        Benders: 1     6853         
          0     0       57.9963                      Benders: 106     6880         
          0     0       57.5304                       Benders: 32     7344         
          0     0       57.3305                       Benders: 26     7573         
          0     0       57.2595                        Benders: 5     7815         
          0     0       57.2415                       Benders: 79     7886         
          0     0       57.0500                       Benders: 29     8263         
          0     0       56.9903                       Benders: 13     8463         
          0     0       56.9730                        Benders: 4     8571         
          0     0       56.9659                        Benders: 3     8634         
          0     0       56.9628                        Benders: 1     8686         
          0     0       56.9621                       Benders: 63     8705         
          0     0       56.8795                       Benders: 22     8966         
          0     0       56.8635                        Benders: 9     9119         
          0     0       56.8566                        Benders: 2     9196         
          0     0       56.8547                       Benders: 73     9253         
          0     0       56.8170                       Benders: 17     9514         
          0     0       56.8044                        Benders: 3     9709         
          0     0       56.8030                        Benders: 5     9783         
          0     0       56.8021                        Benders: 2     9847         
          0     0       56.8010                       Benders: 50     9878         
          0     0       56.7869                       Benders: 12    10043         
          0     0       56.7842                        Benders: 4    10097         
          0     0       56.7837                        Benders: 2    10145         
          0     0       56.7834                        Benders: 1    10170         
          0     0       56.7833                       Benders: 37    10171         
          0     0       56.7766                        Benders: 7    10330         
          0     0       56.7752                        Benders: 2    10386         
          0     0       56.7750                       Benders: 25    10410         
          0     0       56.7726                        Benders: 5    10502         
          0     0       56.7723                       Benders: 23    10527         
          0     0       56.7712                        Benders: 5    10604         
    Tried aggregator 1 time.
    MIP Presolve eliminated 2090 rows and 0 columns.
    MIP Presolve modified 1859 coefficients.
    Reduced MIP has 2746 rows, 1500 columns, and 80907 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.14 sec. (77.36 ticks)
    Probing fixed 0 vars, tightened 526 bounds.
    Probing time = 0.20 sec. (156.58 ticks)
    Tried aggregator 1 time.
    Reduced MIP has 2746 rows, 1500 columns, and 80907 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.03 sec. (28.44 ticks)
    Probing time = 0.03 sec. (16.54 ticks)
    Clique table members: 41065.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 4 threads.
    Root relaxation solution time = 1.97 sec. (861.10 ticks)
    *     0+    0                            1.7425       56.7710              --- 
          0     0       54.0329   405        1.7425       54.0329    13982     --- 
    *     0+    0                            3.1928       54.0329              --- 
          0     0       53.9935   382        3.1928    Benders: 7    14080     --- 
     
    Repeating presolve.
    Tried aggregator 1 time.
    Reduced MIP has 2746 rows, 1500 columns, and 80907 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.06 sec. (46.62 ticks)
    Probing time = 0.05 sec. (18.45 ticks)
    Tried aggregator 1 time.
    Reduced MIP has 2746 rows, 1500 columns, and 80907 nonzeros.
    Reduced MIP has 1000 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.05 sec. (29.68 ticks)
    Represolve time = 0.47 sec. (124.69 ticks)
    Probing time = 0.05 sec. (19.64 ticks)
    Clique table members: 41065.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 4 threads.
    Root relaxation solution time = 1.38 sec. (759.20 ticks)
    *     0+    0                            3.1928       53.9935              --- 
          0     0       53.9331   411        3.1928       53.9331    29035     --- 
          0     2       53.9246   399        3.1928       53.9331    29035     --- 
    Elapsed time = 29.02 sec. (14676.95 ticks, tree = 0.01 MB, solutions = 1)
    *    20+    6                            8.8124       53.9240           511.91%
         20     8        9.1266     1        8.8124       53.9240    29990  511.91%
    *    35+    3                            9.0321       53.9240           497.03%
         39    15        9.0768     2        9.0321       53.9240    30126  497.03%


    I feel like CPLEX first uses Benders to generate Benders cuts and then continues the solution process with the regular B&B? If I am correct, how can I force CPLEX to go with Benders decomposition all along?

    ------------------------------
    S Y
    ------------------------------
    #DecisionOptimization


  • 2.  RE: CPLEX Benders Strategy
    Best Answer

    Community Leadership
    Posted Tue October 05, 2021 11:16 AM
    Edited by System Fri January 20, 2023 04:19 PM
    Hi S,

    You correctly identified that CPLEX uses two phases for Benders Decomposition. It first does the 'Benders cut loop', generating many Benders cuts. I suppose that if it would only use that, this would be what you call 'solving fully by Benders'. But CPLEX will generally stop the cut loop before it solves the model, and go into the 'Benders branch-and-cut' phase. This is basically a regular branch-and-cut on the original model plus the Benders cuts generated during the loop, with additional Benders cuts separated on-the-fly to cut solutions found in the tree.

    Unfortunately, there is no parameter to control if and when CPLEX switches from one phase to the other.

    At the bottom of https://community.ibm.com/community/user/datascience/communities/community-home/all-news?attachments=&communitykey=ab7de0fd-6f43-47a9-8261-33578a231bb7&folder=ce4ab2d3-477e-47ec-870f-d67486fdbbef&pageindex=0&pagesize=12&search=&sort=most_recent&viewtype=row, you will find a number of entries named after conferences where the IBM Decision Optimization team did some presentations. One such conference was INFORMS 2016. During the workshop at this conference, the slides at https://ibm.ent.box.com/s/9ezv4li5252q8t43excr3rrzeno8ak3r were shown.  Starting from slide 29 is the section on Benders Decomposition. I hope this will answer some of the questions you may have.


    ------------------------------
    Xavier
    ------------------------------



  • 3.  RE: CPLEX Benders Strategy

    Posted Tue October 05, 2021 11:55 AM
    Edited by System Fri January 20, 2023 04:46 PM
    Xavier, 

    Thanks for the detailed information. I did not know that CPLEX was using Branch-and-Benders. Honestly, that is pretty cool. Could you share with me the version of CPLEX when this change started? As far as I know, the first Benders strategy designed by CPLEX was using the regular Benders, not the branch-and-cut version. 

    What I understand is that "CPLEX starts with the regular / traditional Benders (solve MP -> Generate a cut -> Update the MP and solve it again) and along the way, it switches to the branch-and-Benders (cuts are generated on the fly on both incumbent and fractional solutions). This means that if solving the model via the traditional Benders is not quite successful, CPLEX decides to turn into branch-and-Benders to accelerate the solution technique."

    Is my interpretation correct?

    ------------------------------
    S Y
    ------------------------------



  • 4.  RE: CPLEX Benders Strategy

    Community Leadership
    Posted Wed October 06, 2021 03:12 AM
    Edited by System Fri January 20, 2023 04:17 PM
    What I understand is that "CPLEX starts with the regular / traditional Benders (solve MP -> Generate a cut -> Update the MP and solve it again) and along the way, it switches to the branch-and-Benders (cuts are generated on the fly on both incumbent and fractional solutions). This means that if solving the model via the traditional Benders is not quite successful, CPLEX decides to turn into branch-and-Benders to accelerate the solution technique."

    Is my interpretation correct?

    Yes, that's entirely correct.

    ------------------------------
    Xavier
    ------------------------------
    #DecisionOptimization


  • 5.  RE: CPLEX Benders Strategy

    IBM Champion
    Posted Tue October 05, 2021 11:18 AM
    I'm pretty sure that Benders cuts are generated all the way through the branch-and-cut process. See, for instance, slide 15 of this presentation, particularly the last box in the flowchart. Also, note that after presolve finished and CPLEX started chewing on the root node, it found a couple of incumbents and also reported seven new Benders cuts.

    The fact that you are not seeing any Benders cuts reported after the root node could mean that CPLEX tried but didn't find any, but it could also be an artifact of the node frequency in the log. If you try a more difficult problem and/or set the log frequency to 1 (print something for every node), you may see more Benders cuts.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 6.  RE: CPLEX Benders Strategy

    Posted Tue October 05, 2021 11:58 AM
    Paul,

    Thanks for your response. 

    Looking at your answer and Xavier's answer, then I guess there is no way to force CPLEX to use the traditional Benders, is there?

    ------------------------------
    S Y
    ------------------------------



  • 7.  RE: CPLEX Benders Strategy

    IBM Champion
    Posted Tue October 05, 2021 01:18 PM
    S Y,

    If by "traditional Benders" you mean  'solve to "optimality" -- add Benders cut -- restart at root' in a loop, no, CPLEX will not automate that for you.

    Paul

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 8.  RE: CPLEX Benders Strategy

    Posted Tue October 05, 2021 02:21 PM
    Yes, that is what I exactly meant. Thanks for the information.

    ------------------------------
    S Y
    ------------------------------



  • 9.  RE: CPLEX Benders Strategy

    Posted Wed October 13, 2021 04:21 PM
    I don't know if I'm in the right spot for this question (it's a very simple question). Is it possible to use the Cplex Benders decomposition for a LP problem not a MILP using for example the cplex option BendersStrategy 1 and identifying manually the partitions?

    Thanks

    Matteo

    ------------------------------
    Matteo Saviozzi
    ------------------------------



  • 10.  RE: CPLEX Benders Strategy

    Community Leadership
    Posted Thu October 14, 2021 04:43 AM
    The Benders algorithm in CPLEX is only supported for MILP problems, not for LP problems, even if you supply the partition manually.

    ------------------------------
    Xavier
    ------------------------------