The model converges slowly

Hi Gurobi experts,

i met some performance issue when i used gurobi 9.5 to solve the MIP model. below is the solver log.

Set parameter MIPGap to value 0.01
2024-03-05 13:42:56,763 - INFO - Set parameter MIPGap to value 0.01
Set parameter TimeLimit to value 200
2024-03-05 13:42:56,763 - INFO - Set parameter TimeLimit to value 200
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
2024-03-05 13:42:57,006 - INFO - Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
2024-03-05 13:42:57,006 - INFO - Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 14523 rows, 7111 columns and 46876 nonzeros
2024-03-05 13:42:57,006 - INFO - Optimize a model with 14523 rows, 7111 columns and 46876 nonzeros
Model fingerprint: 0x1140fc09
2024-03-05 13:42:57,006 - INFO - Model fingerprint: 0x1140fc09
Variable types: 2464 continuous, 4647 integer (0 binary)
2024-03-05 13:42:57,006 - INFO - Variable types: 2464 continuous, 4647 integer (0 binary)
Coefficient statistics:
2024-03-05 13:42:57,007 - INFO - Coefficient statistics:
  Matrix range     [1e+00, 1e+06]
2024-03-05 13:42:57,007 - INFO -   Matrix range     [1e+00, 1e+06]
  Objective range  [1e+00, 7e+03]
2024-03-05 13:42:57,007 - INFO -   Objective range  [1e+00, 7e+03]
  Bounds range     [1e+00, 1e+00]
2024-03-05 13:42:57,007 - INFO -   Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+04]
2024-03-05 13:42:57,007 - INFO -   RHS range        [1e+00, 2e+04]
Presolve removed 12029 rows and 4810 columns
2024-03-05 13:42:57,758 - INFO - Presolve removed 12029 rows and 4810 columns
Presolve time: 0.75s
2024-03-05 13:42:57,758 - INFO - Presolve time: 0.75s
Presolved: 2494 rows, 2301 columns, 11228 nonzeros
2024-03-05 13:42:57,759 - INFO - Presolved: 2494 rows, 2301 columns, 11228 nonzeros
Variable types: 887 continuous, 1414 integer (1414 binary)
2024-03-05 13:42:57,761 - INFO - Variable types: 887 continuous, 1414 integer (1414 binary)

2024-03-05 13:42:57,789 - INFO - 
Root relaxation: objective 4.793681e+03, 1449 iterations, 0.02 seconds (0.02 work units)
2024-03-05 13:42:57,789 - INFO - Root relaxation: objective 4.793681e+03, 1449 iterations, 0.02 seconds (0.02 work units)

2024-03-05 13:42:57,804 - INFO - 
    Nodes    |    Current Node    |     Objective Bounds      |     Work
2024-03-05 13:42:57,804 - INFO -     Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
2024-03-05 13:42:57,804 - INFO -  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

2024-03-05 13:42:57,804 - INFO - 
2024-03-05 13:42:57,804 - INFO -      0     0 4793.68137    0  102          - 4793.68137      -     -    0s
2024-03-05 13:42:57,858 - INFO - H    0     0                    40091.000000 4803.83701  88.0%     -    0s
2024-03-05 13:42:57,859 - INFO - H    0     0                    7286.0000000 4803.83701  34.1%     -    0s
2024-03-05 13:42:57,864 - INFO -      0     0 5073.46086    0  135 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:57,893 - INFO -      0     0 5073.46086    0  140 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:57,904 - INFO -      0     0 5073.46086    0  144 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:57,911 - INFO -      0     0 5073.46086    0  141 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:57,916 - INFO -      0     0 5073.46086    0  141 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:57,920 - INFO -      0     0 5073.46086    0  141 7286.00000 5073.46086  30.4%     -    0s
2024-03-05 13:42:58,032 - INFO -      0     0 5073.46086    0  148 7286.00000 5073.46086  30.4%     -    1s
2024-03-05 13:42:58,071 - INFO -      0     0 5079.60081    0  159 7286.00000 5079.60081  30.3%     -    1s
2024-03-05 13:42:58,083 - INFO -      0     0 5090.48711    0  177 7286.00000 5090.48711  30.1%     -    1s
2024-03-05 13:42:58,093 - INFO -      0     0 5090.54904    0  199 7286.00000 5090.54904  30.1%     -    1s
2024-03-05 13:42:58,100 - INFO -      0     0 5096.16237    0  212 7286.00000 5096.16237  30.1%     -    1s
2024-03-05 13:42:58,200 - INFO - H    0     0                    5828.0000000 5098.68695  12.5%     -    1s
2024-03-05 13:42:58,204 - INFO -      0     0 5099.00000    0  218 5828.00000 5099.00000  12.5%     -    1s
2024-03-05 13:42:58,288 - INFO -      0     0 5099.00000    0  195 5828.00000 5099.00000  12.5%     -    1s
2024-03-05 13:42:58,332 - INFO -      0     0 5099.00000    0  190 5828.00000 5099.00000  12.5%     -    1s
2024-03-05 13:43:02,272 - INFO -   2183   736 5099.00000   99   20 5828.00000 5099.00000  12.5%  58.7    5s
2024-03-05 13:43:07,019 - INFO -   5985  1211 5585.00000   29   27 5828.00000 5099.00000  12.5%  80.1   10s
2024-03-05 13:43:12,399 - INFO -  13438  4696 5754.58245   72   45 5828.00000 5099.00000  12.5%  62.1   15s
2024-03-05 13:43:17,470 - INFO -  18886  7123 5801.00252   64   48 5828.00000 5099.00000  12.5%  65.2   20s
2024-03-05 13:43:22,719 - INFO -  22877  8402 5099.00000   54   51 5828.00000 5099.00000  12.5%  70.0   25s
2024-03-05 13:43:28,212 - INFO -  26235  9400 5100.49778   60   70 5828.00000 5099.00000  12.5%  74.5   31s
2024-03-05 13:43:33,377 - INFO -  28607  9955 5827.00213   70   42 5828.00000 5099.00000  12.5%  77.6   36s
2024-03-05 13:43:37,896 - INFO -  29973 10017 5099.00000   42  190 5828.00000 5099.00000  12.5%  79.1   40s
2024-03-05 13:43:42,291 - INFO -  30235 10339 5099.00000   54   32 5828.00000 5099.00000  12.5%  79.1   45s
2024-03-05 13:43:47,369 - INFO -  33189 11172 infeasible   80      5828.00000 5099.00000  12.5%  78.8   50s
2024-03-05 13:43:52,069 - INFO -  37156 11279 infeasible   74      5828.00000 5099.00000  12.5%  78.8   55s
2024-03-05 13:43:57,487 - INFO -  40736 11107 5099.00000   71   41 5828.00000 5099.00000  12.5%  83.0   60s
2024-03-05 13:44:05,016 - INFO -  42195 10811 infeasible   87      5828.00000 5099.00000  12.5%  85.7   68s
2024-03-05 13:44:08,036 - INFO -  42768 10968 5099.00000   56   46 5828.00000 5099.00000  12.5%  86.9   71s
2024-03-05 13:44:13,075 - INFO -  44105 11006 5099.00000   53   72 5828.00000 5099.00000  12.5%  88.7   76s
2024-03-05 13:44:17,734 - INFO -  45775 11083 5099.00000   80   22 5828.00000 5099.00000  12.5%  90.7   80s
2024-03-05 13:44:23,380 - INFO -  48005 10995 5099.00000   75   22 5828.00000 5099.00000  12.5%  92.7   86s
2024-03-05 13:44:29,522 - INFO -  50141 10876 5585.00000   66   32 5828.00000 5099.00000  12.5%  94.6   92s
2024-03-05 13:44:32,648 - INFO -  51732 10494 5099.00000   69   44 5828.00000 5099.00000  12.5%  95.6   95s
2024-03-05 13:44:38,371 - INFO -  53792 10099 5585.00000   64   38 5828.00000 5099.00000  12.5%  97.3  101s
2024-03-05 13:44:45,192 - INFO -  55648  9809 5099.00000   57   54 5828.00000 5099.00000  12.5%  99.1  108s
2024-03-05 13:44:48,481 - INFO -  56113  9991 5585.00000   62   52 5828.00000 5099.00000  12.5%  99.3  111s
2024-03-05 13:44:55,548 - INFO -  58183  9899 infeasible   90      5828.00000 5099.00000  12.5%   101  118s
2024-03-05 13:44:57,157 - INFO -  59438  9491 5585.00000   83   17 5828.00000 5099.00000  12.5%   102  120s
2024-03-05 13:45:02,437 - INFO -  60604 10292 5099.00000   70   36 5828.00000 5099.00000  12.5%   101  125s
2024-03-05 13:45:07,635 - INFO -  61910 10132 infeasible   73      5828.00000 5099.00000  12.5%   101  130s
2024-03-05 13:45:12,599 - INFO -  63850 10424 infeasible   90      5828.00000 5099.00000  12.5%   102  135s
2024-03-05 13:45:18,100 - INFO -  65122 10760 infeasible  100      5828.00000 5099.00000  12.5%   103  141s
2024-03-05 13:45:22,262 - INFO -  67972 10843 infeasible  108      5828.00000 5099.00000  12.5%   102  145s
2024-03-05 13:45:28,531 - INFO -  70931 10797 infeasible   92      5828.00000 5099.00000  12.5%   102  151s
2024-03-05 13:45:33,330 - INFO -  71998 10704 5099.00000   93   50 5828.00000 5099.00000  12.5%   103  156s
2024-03-05 13:45:39,103 - INFO -  73913 10629 5819.00000   94   34 5828.00000 5099.00000  12.5%   104  162s
2024-03-05 13:45:42,341 - INFO -  74657 10679 5585.00000   87   40 5828.00000 5099.00000  12.5%   104  165s
2024-03-05 13:45:51,257 - INFO -  76536 10425 5180.03924   98   39 5828.00000 5099.00000  12.5%   105  174s
2024-03-05 13:45:55,338 - INFO -  77262 10609 5825.00000  112    6 5828.00000 5099.00000  12.5%   105  178s
2024-03-05 13:46:00,013 - INFO -  78571 10551 5585.00000   96   40 5828.00000 5099.00000  12.5%   106  183s
2024-03-05 13:46:04,373 - INFO -  80010 10277 5801.00000   96   15 5828.00000 5099.00000  12.5%   107  187s
2024-03-05 13:46:09,200 - INFO -  80861 10216 5134.78428   85   66 5828.00000 5099.00000  12.5%   108  192s
2024-03-05 13:46:13,204 - INFO -  81840 10193 5099.00000   79   35 5828.00000 5099.00000  12.5%   108  196s
2024-03-05 13:46:17,021 - INFO -  83218  9781 5587.82268   90   85 5828.00000 5099.00000  12.5%   109  200s

Any suggestion for it?

Michel Soares

March 05, 2024 12:02

Hi!

My first suggestion would be to let it run for longer to understand whether it has already reached an optimal solution and has problem proving its optimality or whether it cannot find a better solution. It seems to me like it may be a case of not being able to prove optimality and you may have the optimal solution in 1 second.

It is important to understand this first to see what makes more sense for you and the parameters you could set to get to where you want.

zhang David

March 06, 2024 04:21

Hi Michel Soares

Thanks for your suggestion. i tried the longer execution time, for example time_limit = 10000s, below is th the part of the log. The gap does not reduce.

2024-03-06 12:18:56,577 - INFO - 4378987 47336 5099.00000 113 13 5828.00000 5099.00000 12.5% 75.8 6835s
4382455 47328 infeasible 128 5828.00000 5099.00000 12.5% 75.8 6840s
2024-03-06 12:19:00,796 - INFO - 4382455 47328 infeasible 128 5828.00000 5099.00000 12.5% 75.8 6840s
4387425 47360 5099.00000 109 13 5828.00000 5099.00000 12.5% 75.8 6845s
2024-03-06 12:19:06,119 - INFO - 4387425 47360 5099.00000 109 13 5828.00000 5099.00000 12.5% 75.8 6845s
4391664 47179 infeasible 108 5828.00000 5099.00000 12.5% 75.8 6850s
2024-03-06 12:19:10,931 - INFO - 4391664 47179 infeasible 108 5828.00000 5099.00000 12.5% 75.8 6850s
4396799 47244 5185.25346 119 15 5828.00000 5099.00000 12.5% 75.8 6855s
2024-03-06 12:19:16,547 - INFO - 4396799 47244 5185.25346 119 15 5828.00000 5099.00000 12.5% 75.8 6855s

why it is difficult to prove the optimality? Do you have any idea about it?

Thanks,

David

March 06, 2024 14:15

Hi David,

It seems like your problem is indeed proving optimality. There are many reasons why this may happen, depending on your model. If you are not familiar with the topic of Weak MIP Formulation, there are some great videos on Gurobi's youtube on the subject. There are some tips that may improve your modelling and fix this proving optimality problem.

Moreover, there are a few parameters that you may want to experiment to fix this issue. The first would be MIPFocus=3. Let this strategy run with longer time and see if it works. If not, you may want to look into other parameters such as Cuts=3 or Presolve=3.

The model converges slowly

Comments

Didn't find what you were looking for?