Move the BestBound

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%

正式なコメント

Michael Winkler

Gurobi Staff

2019年05月16日 12:25

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

Simranjit Kaur

2025年06月23日 03:27 編集済み

This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.

Stefan Bruche

2019年06月04日 13:35

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.

Move the BestBound

コメント

お探しのものを見つけられませんでしたか？