Does more threads mean quicker?
Awaiting user input
Hi,
I want to find a good-quality feasible solution as quick as possible, and do not care about the lower bound. so I have this setting:
model.Params.Cuts = 0
model.Params.MIPFocus = 1
model.Params.RINS = 1
model.Params.NoRelHeurWork = 500
model.Params.TimeLimit = 500
Does this setting let the solver spend all the time to find a better solution? And with this setting, Does a larger model.Params.Threads always be able to find a better solution than a smaller one?
-
Hi,
If you want Gurobi to only spend time finding a good solution in 500s, you can set NoRelHeurTime=500 and TimeLimit=500. This will make Gurobi apply the NoRel Heuristic for the whole time limit duration. Note that you were setting NoRelHeurWork, but this may have different units than seconds.
The other parameters
model.Params.Cuts = 0
model.Params.MIPFocus = 1
model.Params.RINS = 1only become relevant after NoRel has finished, so they won't have an impact in this case. Still, they do not guarantee that the solver will spend all the time finding a better solution, the solver will still work on improving the bound.
In any case, since the NoRel is only a specific heuristic algorithm, you may want to compare the value of the best solution you find by only using this specific heuristic with the value you obtain using other heuristics, which can be controlled with other parameters, like the ones that you mentioned plus for example increasing the Heuristics parameter to 0.5 or 0.75. Even if the solver also works on improving the bound, the best solution you obtain when reaching the time limit may be better than the solution provided by only running NoRel. There is no way to tell which approach is better without testing.
Concerning your Threads question, varying the Threads parameter may impact performance, which may indirectly impact the quality of the solution found. But as described in Does using more Threads make Gurobi faster? the impact of the Threads parameter on performance depends on several factors, like the model structure and type and the number of nodes required to solve it. Again, it is necessary to run tests on different settings of this parameter to decide which one is best.
Elisabeth
0 -
Hi Elisabeth,
Thanks for your advices. Since my problem is NP-hard, It is very hard to solve. So I have to spend all the time finding a better solution.
I have read the Gurobi doc about Heuristic and found some specific heuristic such as PumpPasses, MinRelNodes, ZeroObjNodes. But these three parameters do not work. Some blogs says Gurobi use nearly 30 kinds of heuristic on each node. I have 2 questions:
1. Can all these heuristics be test individually？If yes, can I just use some useful heuristics in my problem?
2. Is there some detailed documents about what heuristics Gurobi has and how they work?
Look forward to your reply.
Best regards,
Peilin
0 -
Thanks for your advices. Since my problem is NP-hard, It is very hard to solve. So I have to spend all the time finding a better solution.
Have you tried other parameters not focusing on heuristics too? Gurobi can solve many instances of NP-hard problems in general, focusing only on the best feasible solution is not always the best strategy. How do the default settings work? Can you share a logfile?
Gurobi uses many different types of heuristics, yes, but not all of them can be controlled individually. You basically identified all the ones that can be controlled individually: NoRel, PumpPasses, MinRelNodes and ZeroObjNodes. You may also want to experiment with the more general Heuristics parameter.
You may also be interested in the ImproveStartTime, ImproveStartNodes and ImproveStartGap parameters to make Gurobi focus all efforts on improving the best objective after a certain amount of time, nodes or gap, respectively.
You may also be interested in providing MIP Starts or Variable Hints to Gurobi. You may obtain the values to feed to the solver for example by solving a smaller, easier problem to find reasonable values for a subset of the variables, or by using external heuristics.
Best regards,
Elisabeth
0 -
Hi Elisabeth,
I did use the MIP Start to give a feasible solution. Here is the log:
Set parameter MIPGap to value 0.05
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[x86] - Darwin 22.3.0 22D68)CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Thread count: 6 physical cores, 12 logical processors, using up to 4 threadsOptimize a model with 158685 rows, 75345 columns and 615792 nonzeros
Model fingerprint: 0xb17de2cd
Variable types: 754 continuous, 74591 integer (74520 binary)
Coefficient statistics:
Matrix range [1e+00, 3e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 3e+04]
RHS range [1e+00, 1e+00]Warning: Completing partial solution with 74428 unfixed non-continuous variables out of 74591
Interrupt request received
User MIP start produced solution with objective 9714 (0.24s)
Loaded user MIP start with objective 9714Presolve removed 94364 rows and 26013 columns
Presolve time: 1.39s
Presolved: 64321 rows, 49332 columns, 263427 nonzeros
Variable types: 754 continuous, 48578 integer (48507 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing primal log only...Concurrent spin time: 0.00s
Solved with primal simplex
Use crossover to convert LP symmetric solution to basic solution...
Root relaxation: objective 0.000000e+00, 20635 iterations, 0.36 seconds (0.30 work units)
Total elapsed time = 5.13s (DegenMoves)Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 0.00000 0 268 9714.00000 0.00000 100% - 5s
0 0 0.00000 0 494 9714.00000 0.00000 100% - 13s
0 0 0.16354 0 450 9714.00000 0.16354 100% - 18s
0 0 0.95652 0 297 9714.00000 0.95652 100% - 23s
0 0 0.95652 0 347 9714.00000 0.95652 100% - 24s
0 0 0.95652 0 407 9714.00000 0.95652 100% - 26s
0 0 0.95652 0 423 9714.00000 0.95652 100% - 30s
0 0 0.95652 0 294 9714.00000 0.95652 100% - 37s
0 0 0.95652 0 380 9714.00000 0.95652 100% - 38s
0 0 0.95652 0 332 9714.00000 0.95652 100% - 47s
0 2 0.95652 0 276 9714.00000 0.95652 100% - 54s
1 4 1.04348 1 274 9714.00000 0.95652 100% 8625 56s
19 14 655.45588 5 335 9714.00000 93.57219 99.0% 1765 60s
36 31 655.45588 8 330 9714.00000 117.27332 98.8% 1388 65s
81 80 702.22222 15 316 9714.00000 158.28193 98.4% 878 70s
95 90 702.22222 18 303 9714.00000 158.28193 98.4% 830 80s
105 103 810.64068 20 319 9714.00000 158.28193 98.4% 795 86s
126 121 702.22222 22 327 9714.00000 158.28193 98.4% 761 92s
167 162 702.22222 33 306 9714.00000 158.28193 98.4% 662 97s
193 200 726.37705 38 310 9714.00000 158.28193 98.4% 630 102s
245 262 737.98333 47 304 9714.00000 158.28193 98.4% 562 105s
305 317 2285.06780 64 306 9714.00000 158.28193 98.4% 517 140s
365 376 1420.66102 78 297 9714.00000 158.28193 98.4% 484 149s
385 419 1420.66102 79 299 9714.00000 158.28193 98.4% 477 161s
453 507 1879.51724 90 309 9714.00000 158.28193 98.4% 445 166s
516 535 1420.75862 100 288 9714.00000 158.28193 98.4% 414 170s
683 684 1502.54717 126 275 9714.00000 158.28193 98.4% 357 179s
715 749 1502.54717 130 276 9714.00000 158.28193 98.4% 352 187s
790 807 1589.09804 145 276 9714.00000 158.28193 98.4% 334 197s
854 882 1589.48000 158 266 9714.00000 158.28193 98.4% 324 200s
949 947 1785.04444 179 257 9714.00000 158.28193 98.4% 306 205s
1178 1021 3713.62295 65 332 9714.00000 158.28193 98.4% 273 217s
1180 1022 737.98333 40 365 9714.00000 158.28193 98.4% 272 234s
1181 1023 3981.18254 177 602 9714.00000 158.28193 98.4% 272 261s
1182 1024 1984.72059 103 707 9714.00000 158.28193 98.4% 272 274sCutting planes:
Gomory: 15
Implied bound: 2
MIR: 112
Flow cover: 130
Zero half: 5
RLT: 1
Relax-and-lift: 4Explored 1182 nodes (681989 simplex iterations) in 300.08 seconds (376.65 work units)
Thread count was 4 (of 12 available processors)Solution count 1: 9714
Time limit reached
Best objective 9.714000000000e+03, best bound 1.590000000000e+02, gap 98.3632%of this setting:
model.Params.Cuts = -1
model.Params.Threads = 4
model.Params.MIPFocus = 1
model.Params.TimeLimit = 300
The solution quality does not get better. But if I set
model.Params.NoRelHeurTime = 300
The solution quality can reach about 6000~7000. So I think the heuristic is a promising way to focus on.
FYI, my problem is basically the balanced connected subgraph partition.
Did I miss some information in the log that can be a hint to speed up the solving?
Best regards,
Peilin0 -
Hi Peilin,
Good to read that the NoRel Heuristic helps improving the best incumbent so much.
Some other things that may help:
- The MIP start that you are providing leaves many binary variables unassigned. As described at the end of How do I use MIP starts?, there are some parameters to control how much effort Gurobi spends on completing a partial MIP start. You may want to try to play with those parameters.
- The objective value of your MIP start is not improved at all during the time limit. What happens if you don't use the MIP start? What happens if you use the NoRel Heuristic with the MIP start?
- The gap is huge, do you have an idea of where the optimal value should be? You can for example let the optimization run for a very long time as a test. This would give a hint on whether Gurobi should focus on improving the incumbent or the bound. If it is the bound that should be improved, then you could try some more aggressive settings for Cuts. If this does not work, you may need to strengthen your model formulation. The Tech Talks linked here give some ideas on how to do this.
Your time limit is quite short, do you need to solve the problem so quickly? What happens for example after 1h?
Best regards,
Elisabeth
0
Please sign in to leave a comment.
Comments
5 comments