Originally posted by: HB0D_欣炜_沈

I've been using MATLAB to call CPLEX 12.8 to solve a large-scale MILP by Benders Decomposition. However, according to the log file in command windows of MATLAB, it seems that it turned to traditional Branch & Cut after a certain time.

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 25481 rows and 3868 columns.
MIP Presolve added 64 rows and 0 columns.
MIP Presolve modified 9216 coefficients.
Aggregator did 9200 substitutions.
Reduced MIP has 25668 rows, 19252 columns, and 92914 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.27 sec. (154.03 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 64 rows and 0 columns.
MIP Presolve added 64 rows and 0 columns.
MIP Presolve modified 32 coefficients.
Reduced MIP has 25668 rows, 19252 columns, and 92914 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.06 sec. (29.87 ticks)
        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth
      0     0   -97829.7809                        Benders: 1        0         
      0     0   -97826.3234                        Benders: 1        8         
      0     0   -97822.9819                        Benders: 1       10         
      0     0   -97819.8329                        Benders: 1       12         
      0     0   -97816.7995                        Benders: 1       14         
      0     0   -97813.8242                        Benders: 1       16         
      0     0   -97810.8618                        Benders: 1       20  
...
...
      0     0   -97791.7387                        Benders: 1     4734         
      0     0   -97791.7377                        Benders: 1     4754         
Tried aggregator 1 time.
MIP Presolve eliminated 64 rows and 0 columns.
MIP Presolve modified 2470 coefficients.
Reduced MIP has 286 rows, 145 columns, and 29261 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (10.44 ticks)
Probing time = 0.00 sec. (0.86 ticks)
Tried aggregator 1 time.
Reduced MIP has 286 rows, 145 columns, and 29261 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (5.70 ticks)
Probing time = 0.00 sec. (0.86 ticks)
Clique table members: 34.
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.50 ticks)
      0     0   -97735.3131    25                 -97735.3131     4876         
Repeating presolve.
Tried aggregator 1 time.
Reduced MIP has 286 rows, 145 columns, and 29261 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (5.70 ticks)
Probing time = 0.00 sec. (0.86 ticks)
Tried aggregator 1 time.
Reduced MIP has 286 rows, 145 columns, and 29261 nonzeros.
Reduced MIP has 144 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (5.70 ticks)
Represolve time = 0.02 sec. (16.46 ticks)
Probing time = 0.00 sec. (0.86 ticks)
Clique table members: 34.
MIP emphasis: balance optimality and feasibility.

MIP search method: traditional branch-and-cut. (Why??)
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.01 sec. (9.50 ticks)
      0     0   -97735.3131    25                 -97735.3131     9752         
      0     2   -97735.3131    25                 -97735.3131     9752                                 0             0
Elapsed time = 54.09 sec. (42885.60 ticks, tree = 0.01 MB, solutions = 0)
    146   104   -97514.8102     1                 -97727.5608    10600                      x34 D    226    218     27
    185   117   -97511.2118     7                 -97727.5608    10646                      x34 D    208    200     23
    207   183   -97675.8081     1                 -97727.5608    10901                      x14 U    238    230     24
    329   294   -97517.8206     1   1.15879e+08   -97725.6538    11381  100.08%             x18 U    197    189     23
    411   312   4.60371e+07     1   1.04272e+08   -97725.4635    11515  100.09%             x45 U    284    268     35
   1788   804        cutoff         2.25953e+07   -97720.3355    17873  100.43%             x16 U   1528   1520     36
   2136  1103   -97508.7325     1   2.25953e+07   -97713.5130    22491  100.43%              x2 U   1871   1863     28
   2353  1211   -97668.7996     1   2.25953e+07   -97710.7812    23787  100.43%            x133 U   1995   1987     28
   2767  1163        cutoff         422662.6364   -97707.2572    30334  123.12%              x5 D   2624    144     18
   3997  1189        cutoff         422662.6364   -97689.8343    35540  123.11%             x46 U   4162   4154     25
   5264   419        cutoff          25922.8392   -97416.1247    39138  475.79%            x127 D   5077   5069     36
Benders cuts applied:  463
Root node processing (before b&c):
  Real time             =   54.09 sec. (42889.30 ticks)
Parallel b&c, 8 threads:
  Real time             =  300.11 sec. (50262.70 ticks)
  Sync time (average)   =    2.51 sec.
  Wait time (average)   =    0.01 sec.
                          ------------
Total (root+branch&cut) =  354.20 sec. (93152.00 ticks)

 

In Line 67, "MIP search method: traditional branch-and-cut. "

Why? How did it happen?

I believe that line 67 has nothing to do with the use of Benders. It is telling you that dynamic search is turned off, and so CPLEX is using traditional branch-and-cut for the master problem. Note on line 84 that CPLEX reports the number of Benders cuts applied.

I don't know why using the automated Benders strategy turns off dynamic search. In the old ("legacy") callback system, using a lazy constraint callback (which one would do if implementing Benders as a "one tree" method) would force CPLEX to turn off dynamic search. Under the new ("generic") callback system, using a generic callback to do the same thing does not force CPLEX to turn off dynamic search. The built in Benders approach will use a lazy constraint callback (or the equivalent) internally, but I would have expected it to be the generic sort.

Originally posted by: HB0D_欣炜_沈

Dear Prof. Rubin, 

Thanks for the answer. Actually I've been trying to turn off all the heuristic and "dynamic search" in CPLEX and simply use Benders Decomposition, and compare the efficiency of Benders Decomposition with conventional Branch & Bound (NOT Branch & Cut). As you can see from Line 1~5 in the code.

To the best of my knowledge, Benders Decomposition cannot be combined with Branch & Bound, right? Oh, you said CPLEX decide to use Branch & Cut (or Bound, whatever) to solve master problem, then, when and why CPLEX decide to start to solve the master problem instead of adding new Benders cut?

I missed the line where you turned off dynamic search. That explains why CPLEX reverted to branch-and-whatever.

Benders decomposition is always combined with branch-and-cut (or branch-and-bound). Benders uses a master problem and one or more subproblems. You solve the master via branch-and-whatever. In its original incarnation (when Jack Benders first published it), you solved the master to optimality, then tested the master solution in the subproblem(s). If it was accepted, you were done. If not, you added one or more cuts to the master and started over. The more modern approach does not wait until an "optimal" solution is found to run the subproblems. You again solve the master using branch-and-whatever, but each time a potential new incumbent is found you test it in the subproblems. If it is accepted in the subproblems, you make it the new incumbent and continue solving the master. If not, you add one or more cuts (via callback), at least one of which is violated by the candidate, and then continue the branch-and-whatever process on the master.