How to determine the speed bottleneck of my Model?
Answered
Hi, I am new to Linear Programming. To solve my problem, I modeling a complex model, and it takes too long to get a result. I want to speed up it, but I cannot point out the bottleneck.
1. I wonder can you help offer some resources about how to understand the meaning of the log. I didn't find any.
2. Here is my log. Can you help me figure out the problem the limits the solving speed of my model. (It took too long, and I killed it)
Academic license - for non-commercial use only - expires 2021-03-19
Using license file /home/duanjiangfei/gurobi.lic
Changed value of parameter NonConvex to 2
Prev: -1 Min: -1 Max: 2 Default: -1
Warning: Q constraint 0 doesn't have a name
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
Thread count: 16 physical cores, 32 logical processors, using up to 32 threads
Optimize a model with 11011 rows, 21194 columns and 22649 nonzeros
Model fingerprint: 0x548c94ce
Model has 1 quadratic objective term
Model has 7214 quadratic constraints
Model has 405460 general constraints
Variable types: 12727 continuous, 8467 integer (4690 binary)
Coefficient statistics:
Matrix range [1e-07, 7e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
QObjective range [4e+00, 4e+00]
Bounds range [1e+00, 8e+02]
RHS range [1e+00, 3e+07]
QRHS range [1e+02, 1e+02]
Presolve removed 2656531 rows and 11621 columns (presolve time = 5s) ...
Presolve added 47563 rows and 0 columns
Presolve removed 0 rows and 4612 columns
Presolve time: 9.98s
Presolved: 92268 rows, 39696 columns, 395186 nonzeros
Presolved model has 13712 SOS constraint(s)
Presolved model has 867 bilinear constraint(s)
Variable types: 16897 continuous, 22799 integer (13012 binary)
Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...
Presolve removed 23144 rows and 29522 columns
Presolved: 69124 rows, 10180 columns, 342777 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 1.011549e+06 3.343188e+10 10s
Concurrent spin time: 0.01s
Solved with dual simplex (dual model)
Root relaxation: objective 0.000000e+00, 7333 iterations, 0.75 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 253 - 0.00000 - - 12s
0 0 0.00000 0 400 - 0.00000 - - 13s
0 0 0.00000 0 384 - 0.00000 - - 13s
0 0 0.00000 0 107 - 0.00000 - - 15s
0 0 0.00000 0 103 - 0.00000 - - 15s
0 0 0.00000 0 96 - 0.00000 - - 16s
0 0 0.00000 0 105 - 0.00000 - - 16s
0 0 0.00000 0 77 - 0.00000 - - 17s
0 0 0.00000 0 89 - 0.00000 - - 17s
0 0 0.00000 0 268 - 0.00000 - - 19s
0 0 0.00000 0 1584 - 0.00000 - - 20s
0 0 0.00000 0 350 - 0.00000 - - 22s
0 0 0.00000 0 350 - 0.00000 - - 23s
0 0 0.00000 0 394 - 0.00000 - - 24s
0 0 0.00000 0 365 - 0.00000 - - 24s
0 0 0.00000 0 218 - 0.00000 - - 26s
0 0 0.00000 0 218 - 0.00000 - - 27s
0 2 0.00000 0 212 - 0.00000 - - 29s
1 4 0.00000 1 231 - 0.00000 - 670 30s
3 8 0.00000 2 926 - 0.00000 - 2886 39s
7 16 0.00000 3 724 - 0.00000 - 4264 45s
15 32 0.00000 4 1008 - 0.00000 - 5114 53s
31 48 0.00000 5 1092 - 0.00000 - 5298 57s
47 64 0.00000 6 1056 - 0.00000 - 4024 70s
79 96 0.00000 8 921 - 0.00000 - 3991 79s
95 115 0.00000 9 894 - 0.00000 - 3457 82s
114 177 0.00000 11 520 - 0.00000 - 3004 91s
176 213 0.00000 18 1031 - 0.00000 - 2293 121s
222 338 0.00000 24 2156 - 0.00000 - 3333 158s
357 697 0.00000 26 3134 - 0.00000 - 3145 224s
848 1655 infeasible 31 - 0.00000 - 2104 335s
2139 3102 0.00000 14 667 - 0.00000 - 1494 428s
4362 3103 0.00000 29 170 - 0.00000 - 997 520s
4364 3104 0.00000 15 326 - 0.00000 - 997 531s
4367 3106 0.00000 11 44 - 0.00000 - 996 539s
4369 3108 0.00000 30 0 - 0.00000 - 995 540s
4371 3109 0.00000 59 0 - 0.00000 - 995 551s
4482 3200 0.00000 19 45 - 0.00000 - 983 555s
4514 3236 0.00000 20 1146 - 0.00000 - 977 626s
4545 3263 0.00000 21 151 - 0.00000 - 973 790s
4582 3303 0.00000 22 40 - 0.00000 - 977 808s
4634 3518 0.00000 23 40 - 0.00000 - 986 931s
4867 3688 0.00000 24 40 - 0.00000 - 965 1039s
5114 4238 0.00000 38 246 - 0.00000 - 982 1287s
H 5568 3931 2.5000000 0.00000 100% 1017 1287s
5747 5469 0.83333 42 2160 2.50000 0.00000 100% 1030 1560s
7805 5206 0.31250 73 3522 2.50000 0.00000 100% 1082 1715s
H 7938 4815 2.4804687 0.00000 100% 1092 1715s
8392 5119 0.31250 77 3140 2.48047 0.00000 100% 1176 1896s
9012 5802 0.42000 79 3531 2.48047 0.00000 100% 1191 2072s
10151 5859 0.31250 87 3900 2.48047 0.00000 100% 1255 2265s
10670 6274 0.31250 93 3861 2.48047 0.00000 100% 1364 2487s
H11007 5804 2.1000000 0.00000 100% 1425 2487s
11366 6117 0.31250 99 3497 2.10000 0.00000 100% 1485 2706s
11912 6344 0.31250 105 4170 2.10000 0.00000 100% 1615 2916s
12463 6704 0.31250 118 3724 2.10000 0.00000 100% 1750 3170s
13124 7434 0.31250 121 3659 2.10000 0.00000 100% 1751 3448s
14062 7908 0.26250 48 2958 2.10000 0.00000 100% 1845 3720s
14726 8287 0.31250 56 4009 2.10000 0.00000 100% 1953 3993s
15300 8931 infeasible 65 2.10000 0.00000 100% 2075 4281s
16136 9319 0.32656 95 3948 2.10000 0.00000 100% 2173 4653s
16657 9841 0.37402 114 3830 2.10000 0.00000 100% 2186 5137s
17417 10867 0.00000 46 244 2.10000 0.00000 100% 2238 5490s
18874 11688 0.47500 102 4052 2.10000 0.00000 100% 2262 5886s
20158 12890 0.48840 132 3615 2.10000 0.00000 100% 2317 6275s
22073 13772 0.00000 35 1028 2.10000 0.00000 100% 2308 6679s
23232 14808 0.83333 49 3066 2.10000 0.00000 100% 2279 7086s
24570 15848 0.00000 38 1877 2.10000 0.00000 100% 2325 7474s
26021 17308 1.25000 54 2971 2.10000 0.00000 100% 2364 7930s
28132 18880 infeasible 69 2.10000 0.00000 100% 2357 8439s
*29814 16971 247 1.3062500 0.00000 100% 2319 8439s
30591 17552 0.62045 94 3617 1.30625 0.00000 100% 2298 8880s
32431 19042 0.60092 102 3928 1.30625 0.00000 100% 2269 9282s
34716 21013 0.00000 171 236 1.30625 0.00000 100% 2246 9678s
-
Official comment
This post is more than three 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 why not try our AI Gurobot?. -
Hi Jiangfei,
You are trying to solve a model with quite a lot of nonlinear constraints - this can be pretty hard even if the number of variables is not very large.
One crucial thing you can see from the log is that the dual bound is not moving from 0. This can make it harder for the solver to find a good search direction. You may be able to improve this by trying to use a different formulation of the problem.
You also didn't show the final statistics that are printed at the end of the run. These show the number of cutting planes that have been added to the model during the optimization. You might want to try different settings for the Cuts parameter to influence this part of the solver.
You can also see that the number of iterations to solve each node is pretty high (1000-2300) compared to the number of iterations necessary to solve the root relaxation (7333). You may want to try a different NodeMethod to check whether you can improve the time it takes to solve these node relaxations and hence to traverse the tree.
Finally, you should try running our automated tuning tool. Just be sure to set the correct tuning target since you don't have a useful MIP gap or dual bound available.
Best of luck with the tuning!
Matthias0 -
Hi, Matthias,
Thanks a lot, I am trying to follow your advices. But I find, maybe the best way to speed up is to reformulate my model with linear constraints only...
Besides, I have a question. I think quadratic constraint and general constraint are nonlinear constraints of different types. For these two type nonlinear constraints, which one is more difficult for solver to optimize?
Best,
Jiangfei
0 -
Hi Jiangfei,
Please excuse me for not coming back earlier.
Probably the most important feature to determine the difficulty of a non-linear model is whether it is convex or not. You should always try to choose a convex formulation of your constraints, if possible.
Cheers,
Matthias0
Post is closed for comments.
Comments
4 comments