Why is Gurobi taking so much time to find a feasible solution with a gap value?
AnsweredHi, 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
-
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
Please sign in to leave a comment.
Comments
2 comments