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