Optimality proof when limited computation time

Hi Gurobi Community!

Suppose I have a limited time to solve a big MILP problem. Gurobi Consume 510 seconds to prove the optimality and then 200 seconds to find the solution using branch and bound and heuristic, which is so fast. However, if I have only 200 seconds to solve the problem, is it possible to avoid the first 510 seconds?

Best,

Hussein

Please see below the log for more info.

MIP_
Set parameter MIPGap to value 0.01
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64)

CPU model: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 581425 rows, 558167 columns and 1605140 nonzeros
Model fingerprint: 0xbefdf75d
Variable types: 446711 continuous, 111456 integer (111456 binary)
Coefficient statistics:
  Matrix range     [1e-03, 1e+05]
  Objective range  [1e+00, 1e+00]
  Bounds range     [3e-05, 3e+04]
  RHS range        [1e+00, 5e+03]
Presolve removed 256855 rows and 237109 columns (presolve time = 5s) ...
Presolve removed 265022 rows and 238060 columns (presolve time = 10s) ...
Presolve removed 266505 rows and 238268 columns
Presolve time: 10.78s
Presolved: 314920 rows, 319899 columns, 980305 nonzeros
Variable types: 213739 continuous, 106160 integer (106160 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...

Root barrier log...

Ordering time: 3.98s

Barrier statistics:
 AA' NZ     : 9.812e+05
 Factor NZ  : 9.045e+06 (roughly 300 MB of memory)
 Factor Ops : 1.712e+09 (less than 1 second per iteration)
 Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0  -1.68608094e+13  2.11024817e+14  1.63e+06 6.26e+04  9.13e+08    21s
   1  -1.06477246e+13  5.92036569e+13  5.38e+05 4.77e+04  2.49e+08    22s
   2  -3.82709447e+12  1.03657513e+13  5.34e+04 3.73e-09  3.06e+07    23s
   3  -6.64789784e+11  1.46576504e+12  5.71e+03 3.26e-09  3.70e+06    24s
   4  -6.96240038e+10  1.82580194e+11  4.41e+02 1.86e-09  3.71e+05    26s
   5  -1.51448662e+10  2.20591724e+10  8.43e+01 1.40e-09  5.17e+04    27s
   6  -4.91189755e+08  3.16262893e+09  2.24e+00 1.40e-09  4.35e+03    28s
   7  -1.05984835e+08  7.83057848e+08  4.51e-01 1.16e-09  1.04e+03    29s
   8  -4.64836635e+07  5.14500886e+08  1.83e-01 9.31e-10  6.53e+02    30s
   9  -6.32895778e+06  2.44033705e+08  9.60e-03 4.66e-10  2.91e+02    31s
  10  -2.51242788e+06  1.11149191e+08  1.91e-03 3.49e-10  1.32e+02    32s
  11  -3.21810255e+05  3.70020515e+07  3.18e-04 3.25e-10  4.33e+01    33s
  12   1.08751177e+06  1.58346275e+07  2.21e-05 2.93e-10  1.71e+01    34s
  13   1.54255599e+06  5.72134922e+06  5.28e-06 3.45e-10  4.85e+00    35s
  14   1.74888744e+06  4.10858758e+06  2.49e-06 3.01e-10  2.74e+00    36s
  15   1.86897535e+06  3.47821823e+06  1.44e-06 2.57e-10  1.87e+00    37s
  16   1.95647565e+06  2.93478846e+06  8.32e-07 2.51e-10  1.14e+00    38s
  17   1.97416292e+06  2.71125036e+06  7.32e-07 2.85e-10  8.56e-01    39s
  18   2.06041429e+06  2.42200300e+06  2.20e-06 2.45e-10  4.20e-01    40s
  19   2.09567885e+06  2.23198288e+06  6.36e-06 2.66e-10  1.58e-01    41s
  20   2.10176286e+06  2.17885120e+06  4.83e-06 3.16e-10  8.96e-02    42s
  21   2.11604719e+06  2.15757485e+06  1.35e-06 2.56e-10  4.83e-02    43s
  22   2.12138063e+06  2.14284094e+06  6.27e-07 2.15e-10  2.49e-02    45s
  23   2.12190773e+06  2.13893904e+06  4.07e-07 2.55e-10  1.98e-02    46s
  24   2.12204813e+06  2.13481567e+06  3.57e-07 2.13e-10  1.48e-02    48s
  25   2.12254752e+06  2.13134648e+06  3.32e-07 2.50e-10  1.02e-02    50s
  26   2.12267190e+06  2.12824612e+06  2.52e-07 2.22e-10  6.47e-03    52s
  27   2.12277398e+06  2.12612162e+06  2.16e-07 2.48e-10  3.89e-03    55s
  28   2.12286872e+06  2.12435427e+06  5.65e-07 2.28e-10  1.73e-03    58s
  29   2.12310196e+06  2.12331252e+06  1.44e-06 2.67e-10  2.45e-04    60s
  30   2.12310281e+06  2.12324428e+06  1.38e-06 2.65e-10  1.64e-04    61s
  31   2.12311286e+06  2.12315944e+06  6.24e-06 2.21e-10  5.41e-05    63s
  32   2.12311284e+06  2.12315440e+06  1.75e-05 2.20e-10  4.82e-05    64s
  33   2.12311268e+06  2.12315213e+06  1.91e-05 2.25e-10  4.55e-05    65s
  34   2.12311411e+06  2.12312235e+06  2.08e-05 2.74e-10  9.35e-06    66s
  35   2.12311693e+06  2.12312124e+06  3.24e-05 2.61e-10  5.09e-06    68s
  36   2.12311688e+06  2.12312123e+06  3.95e-05 2.64e-10  5.07e-06    69s
  37   2.12311701e+06  2.12312144e+06  5.01e-05 2.64e-10  4.39e-06    71s
  38   2.12311730e+06  2.12312120e+06  9.09e-05 3.25e-10  3.68e-06    73s
  39   2.12311972e+06  2.12312124e+06  1.64e-04 3.20e-10  1.49e-06    75s
  40   2.12312272e+06  2.12312119e+06  1.48e-04 2.44e-10  1.72e-07    76s
  41   2.12312406e+06  2.12312120e+06  1.16e-04 3.74e-10  7.61e-08    78s
  42   2.12312267e+06  2.12312119e+06  1.25e-04 2.91e-10  7.12e-08    80s
  43   2.12312212e+06  2.12312119e+06  8.96e-05 3.50e-10  3.87e-09    81s
  44   2.12312199e+06  2.12312119e+06  3.58e-05 4.66e-10  4.34e-12    82s
  45   2.12312214e+06  2.12312119e+06  4.45e-05 1.16e-10  3.52e-13    84s
  46   2.12312184e+06  2.12312119e+06  3.38e-05 2.33e-10  3.80e-15    85s
  47   2.12312275e+06  2.12312119e+06  6.49e-05 2.33e-10  2.83e-15    87s
  48   2.12312330e+06  2.12312119e+06  1.33e-04 2.33e-10  1.63e-15    91s

Barrier performed 48 iterations in 91.06 seconds (23.00 work units)
Sub-optimal termination - objective 2.12310196e+06


Root crossover log...

  176962 DPushes remaining with DInf 0.0000000e+00                92s
   40631 DPushes remaining with DInf 0.0000000e+00               110s
   17010 DPushes remaining with DInf 0.0000000e+00               111s
    3545 DPushes remaining with DInf 0.0000000e+00               115s
    2300 DPushes remaining with DInf 0.0000000e+00               120s
    1676 DPushes remaining with DInf 0.0000000e+00               127s
    1036 DPushes remaining with DInf 0.0000000e+00               133s
     777 DPushes remaining with DInf 0.0000000e+00               137s
     162 DPushes remaining with DInf 0.0000000e+00               144s
       0 DPushes remaining with DInf 0.0000000e+00               145s

   79121 PPushes remaining with PInf 2.6496720e-02               145s
   65990 PPushes remaining with PInf 1.2323183e-01               172s
   43324 PPushes remaining with PInf 5.5989773e-01               176s
   21837 PPushes remaining with PInf 9.6668885e-01               181s
   17562 PPushes remaining with PInf 9.1997246e-01               197s
    7628 PPushes remaining with PInf 1.1755195e+00               265s
    3277 PPushes remaining with PInf 1.7432230e+00               296s
     713 PPushes remaining with PInf 6.8905762e-01               300s
       0 PPushes remaining with PInf 2.6920827e-01               304s

  Push phase complete: Pinf 2.6920827e-01, Dinf 1.1644464e+05    304s


Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
  201705    2.1231245e+06   0.000000e+00   1.164446e+05    304s
  202007    2.1231253e+06   0.000000e+00   1.006448e+04    306s
  202431    2.1231212e+06   0.000000e+00   0.000000e+00    310s
Waiting for other threads to finish...         475s
Concurrent spin time: 188.36s (can be avoided by choosing Method=3)

Solved with barrier

Root relaxation: objective 2.123121e+06, 202431 iterations, 484.93 seconds (116.25 work units)
Total elapsed time = 508.09s
Total elapsed time = 510.32s

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

     0     0 2123121.19    0  781          - 2123121.19      -     -  520s
H    0     0                    1763390.3667 2123121.19  20.4%     -  548s
     0     0 2122669.29    0   35 1763390.37 2122669.29  20.4%     -  683s
H    0     0                    2121748.2957 2122669.29  0.04%     -  712s

Cutting planes:
  Implied bound: 702
  MIR: 3
  Relax-and-lift: 2

Explored 1 nodes (248260 simplex iterations) in 712.79 seconds (206.80 work units)
Thread count was 8 (of 8 available processors)

Solution count 2: 2.12175e+06 1.76339e+06 

Optimal solution found (tolerance 1.00e-02)
Best objective 2.121748295698e+06, best bound 2.122669285293e+06, gap 0.0434%
Time in mins 12.730637760000006

Jaromił Najman

Gurobi Staff

2023年02月06日 09:53

Hi Hussein,

However, if I have only 200 seconds to solve the problem, is it possible to avoid the first 510 seconds?

Unfortunately, it is not possible to skip this part because it is the solution of the root node relaxation which is necessary to get a first valid bound for your model. However, it might be possible to reduce the time spent in this phase significantly.

You can see that the Barrier algorithm converged to a sub-optimal solution

Sub-optimal termination - objective 2.12310196e+06

This can be a sign of a numerically unstable model. This is usually not a problem because Crossover will take care of numerical instabilities by computing a basic solution. This can take longer than usual for numerically difficult models. You can see that the coefficient and bound ranges of your model are not great

Coefficient statistics:
  Matrix range     [1e-03, 1e+05]
  Objective range  [1e+00, 1e+00]
  Bounds range     [3e-05, 3e+04]
  RHS range        [1e+00, 5e+03]

with respectively 8 and 9 order of magnitude differences. You could try to improve the numerical properties of your model by applying some scaling as discussed in our Guidelines for Numerical Issues.

You could try experimenting with parameters to decrease the time spent in the root node relaxation. For example, you could experiment with Presolve, PreSparsify, Method. In particular, you could try Method=2, BarHomogeneous=1. You could also try setting the NoRelHeurTime parameter to 10-20 seconds to try to find a good feasible solution before the root node relaxation.

You might want to try Gurobi's parameter tuning tool. If doing so, you should let the tuning tool run at least for a day or two. I would set the wanted time limit slightly above your desired goal, e.g., 300 seconds. Please note that it is not recommended to overtune a specific instance because often when using too many parameters, those don't have the same effect on the same instance using different data. In general 1-4 parameters should be enough.

If possible, you could share the instance and someone might want to take a look at some parameter settings. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

Best regards,
Jaromił

Optimality proof when limited computation time

コメント

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