CPLEX turned from Benders Decomposition into traditional Branch & Cut algorithm after a certain time.

[Xinwei Shen]

I've been using Benders Decomposition in CPLEX to solve a MILP problem. However, according to the log file, it seems that CPLEX transfered from Benders Decomposition into traditional Branch & Cut in the process. The log file is as followed:

CPXPARAM_Benders_Strategy                        3

CPXPARAM_MIP_Strategy_HeuristicFreq              -1

CPXPARAM_MIP_Limits_CutPasses                    -1

CPXPARAM_MIP_Strategy_RINSHeur                   -1

CPXPARAM_MIP_Strategy_Search                     1

Tried aggregator 2 times.

MIP Presolve eliminated 13065 rows and 6300 columns.

Aggregator did 16 substitutions.

Reduced MIP has 13922 rows, 10452 columns, and 33618 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.03 sec. (26.45 ticks)

Tried aggregator 1 time.

Reduced MIP has 13922 rows, 10452 columns, and 33618 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.01 sec. (10.12 ticks)

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

      0     0       14.0000                       Benders: 52        0         

      0     0       19.5839                       Benders: 39        1         

      0     0       24.9368                       Benders: 26        2         

……
……
……    

      0     0      150.6830                       Benders: 14      109         

      0     0      150.7154                        Benders: 7      111         

      0     0      150.7318                        Benders: 7      116         

      0     0      150.7442                       Benders: 96      117         

      0     0    28771.8618                        28771.8618      213         

Tried aggregator 1 time.

MIP Presolve eliminated 96 rows and 0 columns.

MIP Presolve modified 11979 coefficients.

Reduced MIP has 1667 rows, 144 columns, and 13629 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (5.94 ticks)

Probing time = 0.00 sec. (0.76 ticks)

Tried aggregator 1 time.

Reduced MIP has 1667 rows, 144 columns, and 13629 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (3.26 ticks)

Probing time = 0.00 sec. (0.76 ticks)

Clique table members: 2.

MIP emphasis: balance optimality and feasibility.

MIP search method: traditional branch-and-cut.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.02 sec. (6.59 ticks)

      0     0    28959.2152    16                  28947.2152      254         

Repeating presolve.

Tried aggregator 1 time.

Reduced MIP has 1667 rows, 144 columns, and 13629 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.01 sec. (3.27 ticks)

Probing time = 0.00 sec. (0.76 ticks)

Tried aggregator 1 time.

Reduced MIP has 1667 rows, 144 columns, and 13629 nonzeros.

Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (3.26 ticks)

Represolve time = 0.03 sec. (9.88 ticks)

Probing time = 0.00 sec. (0.76 ticks)

Clique table members: 2.

MIP emphasis: balance optimality and feasibility.

MIP search method: traditional branch-and-cut.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.00 sec. (9.62 ticks)

      0     0    28959.2152    16                  28959.2152      521         

      0     2    28959.2152    16                  28959.2152      521                                 0             0

Elapsed time = 0.98 sec. (755.36 ticks, tree = 0.01 MB, solutions = 0)

*   171+   24                       495108.9933    28968.2152            94.15%

*   191+   69                       445614.4433    29041.2152            93.48%

    191    71    29080.0613    19   445614.4433    29045.4818     3519   93.48%             x12 U     40     24      3

Benders cuts applied:  6498

Root node processing (before b&c):

  Real time             =    0.95 sec. (753.79 ticks)

Parallel b&c, 8 threads:

  Real time             =    2.59 sec. (1035.73 ticks)

  Sync time (average)   =    0.46 sec.

  Wait time (average)   =    0.01 sec.

                          ------------

Total (root+branch&cut) =    3.55 sec. (1789.52 ticks)

How did this happen? Is this related to some settings in YALMIP?

[Johan Löfberg]

nothing yalmip interferes with