Move the BestBound
AnsweredHi,
I have a MIP with several 10 binary variables and I am only interested in fast determination of upper bounds for my maximization problem. To do so I can simply relax the integrality of the problem and use the LP solution of the original problem (takes around 3 min using ‘barrier’ method). To further decrease my upper bound I can iteratively branch a formerly relaxed binary variable, calculate the two respective LPs and get new values for the theoretical ‘BestBound’. However, manual branching is a bit of an overhead.
Therefore, I asked Gurobi to do the work for me and gave him the original MIP. Of cause the first upper bound (root relaxation) is identical with the previously described LP solution. However, even if I ask Gurobi to concentrate on moving the ‘BestBound’ (tried MIPFocus=3 and =2; results are identical) it still seems to look for new incumbents (see solver log) and is almost ignoring the upper bound.
Are there any other solver parameters or approaches I could use to force Gurobi to do branching on a level close to the root node and move the ‘BestBound’? Remember, I am not really interested in any integer solutions here.
Changed value of parameter timelimit to 3600.0
Prev: 1e+100 Min: 0.0 Max: 1e+100 Default: 1e+100
Changed value of parameter MIPFocus to 3
Prev: 0 Min: 0 Max: 3 Default: 0
Changed value of parameter NodeMethod to 2
Prev: 1 Min: 1 Max: 2 Default: 1
Changed value of parameter DegenMoves to 0
Prev: 1 Min: 1 Max: 2000000000 Default: 1
Changed value of parameter Heuristics to 0.0
Prev: 0.05 Min: 0.0 Max: 1.0 Default: 0.05
Changed value of parameter Cuts to 0
Prev: 1 Min: 1 Max: 3 Default: 1
Changed value of parameter DisplayInterval to 1
Prev: 5 Min: 1 Max: 2000000000 Default: 5
Changed value of parameter method to 2
Prev: 1 Min: 1 Max: 5 Default: 1
Optimize a model with 1410575 rows, 1252899 columns and 4380591 nonzeros
Variable types: 1252861 continuous, 38 integer (38 binary)
Coefficient statistics:
Matrix range [4e04, 4e+04]
Objective range [1e+00, 1e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+02]
Presolve removed 381227 rows and 394367 columns (presolve time = 1s) ...
Presolve removed 588743 rows and 601882 columns (presolve time = 2s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 3s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 4s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 5s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 6s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 7s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 8s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 9s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 10s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 11s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 12s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 15s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 19s) ...
Presolve removed 623925 rows and 604750 columns (presolve time = 22s) ...
Presolve removed 623925 rows and 604750 columns
Presolve time: 21.75s
Presolved: 786650 rows, 648149 columns, 2216799 nonzeros
Variable types: 631170 continuous, 16979 integer (16979 binary)
Presolved: 786650 rows, 648149 columns, 2216799 nonzeros
Root barrier log...
Ordering time: 0.00s
Barrier statistics:
Dense cols : 40
AA' NZ : 2.760e+06
Factor NZ : 1.199e+07 (roughly 700 MBytes of memory)
Factor Ops : 3.037e+08 (less than 1 second per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.92865463e+07 1.51858518e+10 6.51e+02 8.87e+02 6.75e+04 25s
1 2.78978606e+07 8.51771288e+09 6.01e+02 1.36e+03 5.63e+04 25s
2 2.42331112e+07 6.67841380e+09 5.04e+02 7.70e+02 4.65e+04 26s
3 7.56714679e+06 4.27199952e+09 1.18e+02 1.76e+02 1.19e+04 26s
4 6.64017940e+06 2.87428482e+09 9.99e+01 4.80e+01 8.88e+03 27s
5 5.82657770e+06 2.49463580e+09 8.50e+01 3.16e+01 7.32e+03 27s
...
136 1.76509764e+05 1.76509347e+05 1.25e08 1.13e09 2.01e07 90s
137 1.76509765e+05 1.76509351e+05 1.23e08 3.79e09 2.00e07 91s
138 1.76509765e+05 1.76509356e+05 1.19e08 3.75e09 1.98e07 92s
139 1.76509765e+05 1.76509356e+05 1.19e08 3.75e09 1.97e07 93s
140 1.76509765e+05 1.76509357e+05 1.19e08 4.31e09 1.97e07 94s
Barrier performed 140 iterations in 93.86 seconds
Suboptimal termination  objective 1.76509763e+05
Root crossover log...
350994 DPushes remaining with DInf 1.5329488e02 96s
90905 DPushes remaining with DInf 0.0000000e+00 97s
16981 DPushes remaining with DInf 0.0000000e+00 98s
7568 DPushes remaining with DInf 0.0000000e+00 99s
0 DPushes remaining with DInf 4.1660391e11 100s
66168 PPushes remaining with PInf 2.0379315e03 100s
48287 PPushes remaining with PInf 2.2113399e03 100s
33506 PPushes remaining with PInf 2.0752996e03 101s
20654 PPushes remaining with PInf 1.7316501e03 102s
13999 PPushes remaining with PInf 1.6986589e03 103s
9809 PPushes remaining with PInf 1.6966971e03 104s
14 PPushes remaining with PInf 0.0000000e+00 106s
0 PPushes remaining with PInf 0.0000000e+00 108s
Push phase complete: Pinf 0.0000000e+00, Dinf 5.0710192e02 108s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
356492 1.7650975e+05 0.000000e+00 5.071019e02 108s
356620 1.7650975e+05 0.000000e+00 0.000000e+00 108s
356620 1.7650975e+05 0.000000e+00 0.000000e+00 109s
Root relaxation: objective 1.765097e+05, 356620 iterations, 86.28 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 176509.75 0 14622  176509.75   112s
0 0 176509.75 0 14622  176509.75   210s
0 2 176509.75 0 14622  176509.75   474s
1 4 176509.90 1 6461  176509.75  665431 1050s
3 8 176515.61 2 3  176509.90  629990 1364s
7 12 183739.22 3 4697  176510.30  462541 1672s
11 12 176515.61 3 1  176510.30  459721 1844s
15 15 177359.29 4 6138  176510.30  374046 2231s
19 13 178220.43 4 2357  176510.30  374649 2476s
* 21 14 5 179243.0231 176510.30 1.52% 375026 2476s
* 22 15 5 179141.3234 176510.30 1.47% 380957 2476s
23 13 177363.63 5 4697 179141.32 176510.30 1.47% 378938 2719s
27 19 177359.29 5 5178 179141.32 176510.30 1.47% 375310 2916s
* 30 17 7 177237.2725 176510.30 0.41% 367394 2916s
32 10 cutoff 6 177237.27 176514.46 0.41% 354237 3201s
Explored 39 nodes (13281850 simplex iterations) in 3600.88 seconds
Thread count was 8 (of 8 available processors)
Solution count 3: 177237 179141 179243
Time limit reached
Best objective 1.772372725346e+05, best bound 1.765144620715e+05, gap 0.4078%

Official comment
Dear Stefan,
what bounds do you get when you manually branch on a variable (do you have special knowledge which variable will have a big impact on moving the dual bound or does it not really matter)?
Could you make your instance available for us, best in MPS format (compressed with 7zip, bzip2, gzip ...) via a dropbox (or some other data storage website) link?
Some guesses what you can try:
1. set DUALREDUCTIONS=0
2. or set the branching priorities on (some of) your 38 binary variables, see http://www.gurobi.com/documentation/8.1/refman/branchpriority.html
Best,
Michael

Thanks for your response and your helpful hints Michael!
There is one binary variable (X) that has a larger influence on the BestBound (Root=176510; X_0=177207; X_1=177359). So branching this variable would definitely help. But of cause, the identification of this variable is the tough part and largely depends on experience or luck. So I cannot blame Gurobi. I did some experiments trying to use the reduced costs of the relaxed binary variables to push the solver into the right direction, but my success was rather moderate.
0
Please sign in to leave a comment.
Comments
2 comments