Move the BestBound
Answered
Hi,
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 [4e-04, 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.25e-08 1.13e-09 2.01e-07 90s
137 -1.76509765e+05 -1.76509351e+05 1.23e-08 3.79e-09 2.00e-07 91s
138 -1.76509765e+05 -1.76509356e+05 1.19e-08 3.75e-09 1.98e-07 92s
139 -1.76509765e+05 -1.76509356e+05 1.19e-08 3.75e-09 1.97e-07 93s
140 -1.76509765e+05 -1.76509357e+05 1.19e-08 4.31e-09 1.97e-07 94s
Barrier performed 140 iterations in 93.86 seconds
Sub-optimal termination - objective -1.76509763e+05
Root crossover log...
350994 DPushes remaining with DInf 1.5329488e-02 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.1660391e-11 100s
66168 PPushes remaining with PInf 2.0379315e-03 100s
48287 PPushes remaining with PInf 2.2113399e-03 100s
33506 PPushes remaining with PInf 2.0752996e-03 101s
20654 PPushes remaining with PInf 1.7316501e-03 102s
13999 PPushes remaining with PInf 1.6986589e-03 103s
9809 PPushes remaining with PInf 1.6966971e-03 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.0710192e-02 108s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
356492 -1.7650975e+05 0.000000e+00 5.071019e-02 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