Why is Gurobi taking so much time to find a feasible solution with a gap value?
回答済みHi, I have used Gurobi to solve a model. However, it takes a long time to find a feasible solution with a gap value. Is there any solution to speed up the running time? Here is the output. It takes over 7000s to find the first feasilbe solution with a gap value.
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 98150 rows, 1555757 columns and 16206463 nonzeros
Model fingerprint: 0xacbcc507
Model has 14 quadratic constraints
Model has 21 general constraints
Variable types: 63 continuous, 1555694 integer (1555687 binary)
Coefficient statistics:
Matrix range [4e-04, 3e+02]
QMatrix range [1e+00, 1e+00]
Objective range [1e+01, 2e+01]
Bounds range [1e+00, 3e+04]
RHS range [1e+00, 2e+04]
QRHS range [9e+06, 9e+06]
Presolve removed 88965 rows and 1491092 columns (presolve time = 5s) ...
Presolve removed 88797 rows and 1343750 columns
Presolve time: 7.93s
Presolved: 9367 rows, 212007 columns, 1074521 nonzeros
Presolved model has 14 SOS constraint(s)
Presolved model has 7 bilinear constraint(s)
Variable types: 147356 continuous, 64651 integer (64525 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 0.04s
Barrier statistics:
AA' NZ : 1.989e+05
Factor NZ : 4.964e+05 (roughly 100 MB of memory)
Factor Ops : 2.817e+07 (less than 1 second per iteration)
Threads : 2
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 5.23178726e+06 -1.40362386e+06 3.84e+08 4.23e-01 7.50e+04 9s
1 1.79113562e+06 -1.52481758e+06 1.44e+08 2.93e+00 2.83e+04 9s
2 9.60233848e+04 -5.74396568e+05 6.28e+06 3.20e-14 1.25e+03 9s
3 4.43239445e+03 -2.62861018e+05 2.40e+05 3.73e-14 4.82e+01 9s
4 1.21867285e+03 -1.57414991e+05 2.84e+04 3.38e-14 6.02e+00 10s
5 9.53097620e+02 -1.11965662e+05 1.04e+04 2.13e-14 2.29e+00 10s
6 8.75149146e+02 -6.64253506e+04 4.73e+03 5.68e-14 1.04e+00 10s
7 8.82955784e+02 -3.91008270e+04 1.94e+03 7.11e-14 4.32e-01 10s
8 1.04242787e+03 -2.36862306e+04 1.38e+03 7.82e-14 2.60e-01 10s
9 1.06384719e+03 -1.72552970e+04 9.02e+02 4.26e-14 1.61e-01 10s
10 1.05617726e+03 -1.13926948e+04 2.95e+02 1.99e-13 6.40e-02 10s
11 1.05305463e+03 -8.97379027e+03 1.33e+02 1.71e-13 3.94e-02 10s
12 1.05220100e+03 -8.42702960e+03 9.52e+01 9.95e-14 3.34e-02 10s
13 1.05185305e+03 -6.81546025e+03 8.08e+01 1.14e-13 2.77e-02 10s
Barrier performed 13 iterations in 9.99 seconds (9.48 work units)
Barrier solve interrupted - model solved by another algorithm
Concurrent spin time: 0.06s
Solved with primal simplex
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
39965 9.5691301e+02 0.000000e+00 0.000000e+00 10s
Root relaxation: objective 9.569130e+02, 39965 iterations, 1.76 seconds (1.44 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 956.91301 0 97 - 956.91301 - - 10s
0 0 956.97926 0 97 - 956.97926 - - 10s
0 0 957.04542 0 97 - 957.04542 - - 10s
0 0 957.11148 0 97 - 957.11148 - - 10s
0 0 957.17744 0 97 - 957.17744 - - 10s
0 0 957.24331 0 97 - 957.24331 - - 10s
0 0 957.30909 0 97 - 957.30909 - - 10s
0 0 957.37477 0 97 - 957.37477 - - 10s
0 0 957.44036 0 97 - 957.44036 - - 10s
0 0 957.50585 0 97 - 957.50585 - - 10s
……
0 0 1013.09994 0 383 - 1013.09994 - - 380s
0 2 1013.09994 0 378 - 1013.09994 - - 394s
5 2 1015.02368 3 355 - 1014.31056 - 1579 400s
96 44 1018.32905 18 299 - 1017.48220 - 180 405s
175 117 1018.41359 28 285 - 1017.48220 - 141 410s
302 175 1022.88357 49 259 - 1017.48220 - 113 415s
414 251 1024.07881 66 183 - 1017.48220 - 106 420s
582 353 1023.52491 91 199 - 1017.48220 - 93.9 425s
823 523 infeasible 142 - 1017.48220 - 79.8 430s
……
273288 166223 1019.30635 62 210 - 1019.30635 - 17.1 7018s
273985 166594 1019.46502 156 97 - 1019.30635 - 17.0 7027s
274624 166910 1023.76780 210 88 - 1019.30635 - 17.0 7042s
275198 167182 1025.42970 256 88 - 1019.30635 - 17.0 7050s
*275713 165417 344 1025.2196009 1019.30635 0.58% 17.0 7050s
275824 165367 cutoff 343 1025.21960 1019.30635 0.58% 17.0 7073s
H275826 163265 1024.4393728 1019.30635 0.50% 17.0 7073s
H275827 154484 1023.8898198 1019.30635 0.45% 17.0 7073s
275830 154605 1019.30635 40 251 1023.88982 1019.30635 0.45% 17.0 7090s
H275855 154605 1023.8895206 1019.30635 0.45% 17.0 7090s
H275994 154605 1023.8893505 1019.30635 0.45% 17.0 7090s
275995 154694 1019.30635 42 178 1023.88935 1019.30635 0.45% 17.0 7109s
---
276859 143703 1019.30635 132 65 1023.61021 1019.30635 0.42% 17.0 7204s
276870 143776 1019.30635 133 65 1023.61021 1019.30635 0.42% 17.0 7223s
H276893 143776 1023.6065478 1019.30635 0.42% 17.0 7223s
H276937 143776 1023.6065144 1019.30635 0.42% 17.0 7223s
H276961 143315 1023.5908176 1019.30635 0.42% 17.0 7223s
276986 143437 infeasible 175 1023.59082 1019.30635 0.42% 17.0 7238s
277239 143528 cutoff 199 1023.59082 1019.30635 0.42% 17.1 7255s
277354 143902 1019.33095 54 111 1023.59082 1019.30635 0.42% 17.1 7271s
277805 143978 infeasible 153 1023.59082 1019.30635 0.42% 17.1 7289s
278000 144059 cutoff 174 1023.59082 1019.30635 0.42% 17.1 7304s
……
364098 206499 1019.30635 47 349 1023.59082 1019.30635 0.42% 18.7 9903s
364496 206722 1019.30635 107 102 1023.59082 1019.30635 0.42% 18.7 9915s
364886 206937 1021.59710 117 78 1023.59082 1019.30635 0.42% 18.8 9931s
365173 207153 infeasible 182 1023.59082 1019.30635 0.42% 18.8 9945s
365460 207349 1023.52333 185 69 1023.59082 1019.30635 0.42% 18.9 9957s
365750 207646 1019.30635 53 192 1023.59082 1019.30635 0.42% 18.9 9970s
366119 207779 infeasible 159 1023.59082 1019.30635 0.42% 19.0 9984s
366430 208014 infeasible 60 1023.59082 1019.30635 0.42% 19.1 9999s
Cutting planes:
Gomory: 165
Lift-and-project: 160
MIR: 335
StrongCG: 49
Flow cover: 85
RLT: 680
Explored 366745 nodes (7161324 simplex iterations) in 10001.77 seconds (7779.83 work units)
Thread count was 8 (of 8 available processors)
Solution count 10: 1023.59 1023.61 1023.61 ... 1023.89
Time limit reached
Best objective 1.023590817558e+03, best bound 1.019306354110e+03, gap 0.4186%
Thank you.
0
-
正式なコメント
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
In order to improve the feasible solution finding process you could start by setting the MIPFocus parameter to 1. You could also try one of the following three: ImproveStartNodes, ImproveStartGap, and ImproveStartTime.
If possible, you could provide a (partial) starting solution.Please also have a look into important parameters for MIP models.
0 -
Thank you very much, Karbstein.
0
投稿コメントは受け付けていません。
コメント
3件のコメント