How to improve the BestBound in my Gurobi model?

Hi! My model might solve the problem for small instances, but for larger instances the BestBound hardly changes. I used a MIP Start and changed several parameters looking for some change but it almost doesn't change from this 80% gap. Are there any tips or settings I can change to improve this gap?
I copy a snippet of the log below.

Thank you in advance,

Lucia

Gurobi 9.1.2 (mac64) logging started Thu Feb 17 10:42:35 2022

Changed value of parameter LogFile to m_8_171.log
   Prev:   Default: 
Changed value of parameter StartNodeLimit to 20000
   Prev: -1  Min: -3  Max: 2000000000  Default: -1
Changed value of parameter NoRelHeurTime to 1.0
   Prev: 0.0  Min: 0.0  Max: inf  Default: 0.0
Changed value of parameter Method to 3
   Prev: -1  Min: -1  Max: 5  Default: -1
Changed value of parameter FeasibilityTol to 0.01
   Prev: 1e-06  Min: 1e-09  Max: 0.01  Default: 1e-06
Changed value of parameter BarConvTol to 0.0
   Prev: 1e-08  Min: 0.0  Max: 1.0  Default: 1e-08
Changed value of parameter DegenMoves to 0
   Prev: -1  Min: -1  Max: 2000000000  Default: -1
Changed value of parameter StartNodeLimit to 10
   Prev: 20000  Min: -3  Max: 2000000000  Default: -1
Read MIP start from file marlim_170.mst
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 588383 rows, 62179 columns and 3050021 nonzeros
Model fingerprint: 0xe2fee860
Variable types: 587 continuous, 61592 integer (61592 binary)
Coefficient statistics:
  Matrix range     [1e+00, 7e+04]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 7e+04]

Warning: Completing partial solution with 61421 unfixed non-continuous variables out of 61592
User MIP start produced solution with objective 1827.26 (178.94s)
Loaded user MIP start with objective 1827.26
Processed MIP start in 178.97 seconds

Presolve removed 7353 rows and 1084 columns (presolve time = 5s) ...
Presolve removed 7354 rows and 1084 columns (presolve time = 10s) ...
Presolve removed 7354 rows and 1084 columns
Presolve time: 10.02s
Presolved: 581029 rows, 61095 columns, 3019180 nonzeros
Variable types: 217 continuous, 60878 integer (60878 binary)
Starting NoRel heuristic

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Root barrier log...

Ordering time: 4.41s

Barrier statistics:
 Dense cols : 375
 Free vars  : 542
 AA' NZ     : 1.669e+06
 Factor NZ  : 5.932e+06 (roughly 330 MBytes of memory)
 Factor Ops : 8.462e+09 (less than 1 second per iteration)
 Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0  -8.40040033e+07 -0.00000000e+00  2.63e+02 2.56e+02  2.72e+03   205s
   1  -5.43421945e+07  2.39255266e+01  7.82e+01 3.29e+03  2.03e+03   206s
   2  -4.97529570e+07  1.99048356e+03  9.03e+00 4.63e+02  3.44e+02   207s
   3  -3.53749130e+07  1.66002461e+03  1.08e+00 7.00e+01  8.21e+01   208s
   4  -1.82440914e+07  1.60015731e+03  2.49e-01 6.13e+01  4.28e+01   209s
   5  -1.42450914e+07  1.24870057e+03  1.73e-01 3.59e+01  2.86e+01   210s
   6  -1.22449317e+06  5.80404948e+02  7.94e-09 1.71e+00  1.93e+00   211s
   7  -2.36341238e+05  4.53004739e+02  1.50e-09 2.16e-03  3.37e-01   213s
   8  -1.47464822e+04  4.08430993e+02  6.50e-10 2.82e-04  2.16e-02   215s
   9  -5.62791648e+02  3.26287865e+02  1.01e-08 7.75e-06  1.27e-03   217s
  10  -1.53479583e+02  3.12964442e+02  5.66e-09 5.87e-06  6.64e-04   218s
  11  -9.33893166e+00  2.93576468e+02  3.65e-09 4.04e-06  4.31e-04   219s
  12   1.10654531e+02  2.90056018e+02  1.05e-06 3.72e-06  2.55e-04   220s
  13   2.45891540e+02  2.96596979e+02  1.31e-07 7.65e-07  7.22e-05   222s
  14   2.76659409e+02  2.88764544e+02  2.99e-08 5.26e-09  1.72e-05   223s
  15   2.88687095e+02  2.88699427e+02  6.78e-10 1.52e-09  1.75e-08   224s
  16   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   225s
  17   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   226s
  18   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   227s
  19   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   228s
  20   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   229s
  21   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   230s
  22   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   231s
  23   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   232s
  24   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   233s
  25   2.88687095e+02  2.88699427e+02  4.64e-09 4.85e-09  1.75e-08   234s

Barrier performed 25 iterations in 234.11 seconds
Sub-optimal termination - objective 2.88687095e+02


Root crossover log...

   60505 DPushes remaining with DInf 0.0000000e+00               234s
   56771 DPushes remaining with DInf 0.0000000e+00               235s
   51429 DPushes remaining with DInf 0.0000000e+00               240s
   46255 DPushes remaining with DInf 0.0000000e+00               245s
   41090 DPushes remaining with DInf 0.0000000e+00               250s
   35782 DPushes remaining with DInf 0.0000000e+00               255s
   30331 DPushes remaining with DInf 0.0000000e+00               260s
   24340 DPushes remaining with DInf 0.0000000e+00               265s
   19854 DPushes remaining with DInf 0.0000000e+00               270s
   14701 DPushes remaining with DInf 0.0000000e+00               275s
   10841 DPushes remaining with DInf 0.0000000e+00               280s
    6183 DPushes remaining with DInf 0.0000000e+00               285s
    1746 DPushes remaining with DInf 0.0000000e+00               290s
    1211 DPushes remaining with DInf 0.0000000e+00               296s
     826 DPushes remaining with DInf 0.0000000e+00               301s
     165 DPushes remaining with DInf 0.0000000e+00               306s
       0 DPushes remaining with DInf 0.0000000e+00               307s

       0 PPushes remaining with PInf 0.0000000e+00               307s

  Push phase complete: Pinf 0.0000000e+00, Dinf 7.0084633e-12    307s


Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
   48588    2.8869914e+02   0.000000e+00   0.000000e+00    307s
   48588    2.8869914e+02   0.000000e+00   0.000000e+00    308s
   48588    2.8869914e+02   0.000000e+00   0.000000e+00    309s

Solved with barrier

Root relaxation: objective 2.886991e+02, 48588 iterations, 113.70 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  288.69914    0  954 1827.25864  288.69914  84.2%     -  388s
     0     0  327.48195    0  802 1827.25864  327.48195  82.1%     -  673s
H    0     0                    1819.1880610  327.48195  82.0%     -  912s
     0     0          -    0      1819.18806  327.48195  82.0%     - 5785s

Cutting planes:
  Gomory: 1
  Cover: 1
  Implied bound: 159
  Clique: 1
  MIR: 5
  Flow cover: 14
  Zero half: 20
  RLT: 3
  Relax-and-lift: 13

Explored 1 nodes (536120 simplex iterations) in 5787.11 seconds
Thread count was 4 (of 4 available processors)

Solution count 2: 1819.19 1827.26 

Time limit reached
Best objective 1.819188060954e+03, best bound 3.274819520606e+02, gap 81.9985%

User-callback calls 68136, time in user-callback 1.16 sec
Changed value of parameter outputFlag to 1
   Prev: 0  Min: 0  Max: 1  Default: 1
Changed value of parameter presolve to 0
   Prev: -1  Min: -1  Max: 2  Default: -1
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 588383 rows, 62179 columns and 3050021 nonzeros
Model fingerprint: 0xe0fc6911
Coefficient statistics:
  Matrix range     [1e+00, 7e+04]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 7e+04]

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...


Barrier performed 0 iterations in 2.71 seconds
Barrier solve interrupted - model solved by another algorithm


Solved with dual simplex
Solved in 447 iterations and 2.74 seconds
Optimal objective  1.819188061e+03

Jaromił Najman

Gurobi Staff

February 18, 2022 13:12

Hi Lucia,

There are many ways to try to improve the performance for your model. First of all, please try the latest Gurobi version 9.5.1.

You are setting the NoRelHeurTime parameter to \(1\) which allows for only exactly \(1\) second of the no relaxation heuristic. You should try giving it some more time, e.g., \(120\) seconds or more.

You are setting the parameter StartNodeLimit twice. I would try leaving it at its default value and only experiment with it if Gurobi is not able to generate a feasible solution out of your MIP start.

Barrier is the winning algorithm for the root relaxation, thus you could set Method=2 to gain some more seconds.

I also noticed that you are relaxing the FeasibilityTol and BarConvTol quite a bit. It is not recommended to loosen these tolerance by that much unless you have a really good reason for this, e.g., the model accuracy and/or numerics are really bad.

The log also shows that you are use callbacks. Do you use them to add lazy constraints or user cuts? If yes, is the number of your lazy constraints/user cuts finite such that you could try adding them to the model from start? It often helps to add all lazy constraints/user cuts to the model from start, because then Gurobi can use these constraints in its presolving step.

Do you have an idea whether the best bound has to be improved or rather a better feasible solution has to be found? If you have a guess about the optimal value of this model, you could try experimenting with the MIPFocus parameter.

You say smaller instances have been solved successfully. You could try using Gurobi's tuning tool to find suitable parameters for the smaller instances and check whether these also help for the large one.

Best regards,
Jaromił

How to improve the BestBound in my Gurobi model?

Comments

Didn't find what you were looking for?