MIP Performance based on simplex and barrier
Answered
Hi!
I am working with a MIQP problem and I notice some notable differences when the solution process performs with dual simplex and barrier algorithms. For example, in the root the barrier performs much better than simplex (but it does not get a basis solution); in contrast, the simpex performs much better in the branch and bound process. So, I would like to ask the following questions:
1) If barrier is faster than simplex for a given problem (e.g., in the root), why is slower in branch & bound? (I guess that restart plays an important role).
2) Is there a way to perform barrier plus crossover in the root and then simplex for the branches (maybe it can be cheaper than only simplex)?
3) In the barrier case there is a node (between 704 and 729) that takes excessive long time to be processed (the accumulated time pass from 9277s to 38180s). Why could that be happening? I know that after numerical issues the node is posponed, but this is not the case, so, the long time is maybe because of heuristics? if this is the case, how much time Gurobi can invest for an heuristic? is there a limit?
Thanks in advance
Additionallly, I share the results with each method below :
Coefficient statistics:
Matrix range [1e-07, 3e+03]
Objective range [2e-05, 2e+03]
QObjective range [2e-01, 2e+00]
Bounds range [1e+00, 2e+04]
RHS range [1e-04, 2e+04]
Variable types: 222022 continuous, 5495 integer (1951 binary)
Simplex:
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -6.3018570e+03 0.000000e+00 0.000000e+00 18s
16508 1.8515745e+04 2.849357e+04 0.000000e+00 20s
35255 3.3155281e+04 2.336307e+04 0.000000e+00 25s
....
427776 8.5018492e+04 1.285808e-06 0.000000e+00 2463s
427786 8.5018491e+04 0.000000e+00 0.000000e+00 2464s
Root relaxation: objective 8.501849e+04, 427786 iterations, 2446.01 seconds (5910.42 work units)
Another try with MIP start
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 85018.4914 0 2102 - 85018.4914 - - 2945s
0 0 85021.9784 0 2104 - 85021.9784 - - 3442s
0 0 85021.9852 0 2105 - 85021.9852 - - 3446s
....
2299 2365 86385.4734 254 1123 - 85125.2128 - 308 8710s
2364 2434 86405.1694 255 1122 - 85125.2128 - 313 10880s
2433 2526 86472.6141 258 1118 - 85125.2128 - 637 10975s
.....
34657 24916 cutoff 2867 87498.1752 85133.7229 2.70% 286 70646s
Barrier:
Barrier statistics:
Dense cols : 1526
AA' NZ : 2.350e+06
Factor NZ : 1.249e+07 (roughly 300 MB of memory)
Factor Ops : 4.757e+09 (less than 1 second per iteration)
Threads : 5
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 4.30804679e+10 -4.79082193e+10 8.25e+04 9.36e+02 1.17e+06 20s
1 3.01971024e+10 -3.49903758e+10 6.81e+04 7.83e+02 9.83e+05 20s
......
76 8.50189906e+04 8.50189856e+04 7.24e-11 1.83e-09 8.26e-09 40s
77 8.50189900e+04 8.50189890e+04 4.45e-09 3.72e-09 1.57e-09 40s
Barrier solved model in 77 iterations and 40.33 seconds (30.64 work units)
Optimal objective 8.50189900e+04
Root relaxation: objective 8.501899e+04, 0 iterations, 22.60 seconds (19.82 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 85018.9900 0 2121 - 85018.9900 - - 51s
Another try with MIP start
0 0 85018.9900 0 2104 - 85018.9900 - - 77s
0 0 85022.5595 0 2107 - 85022.5595 - - 124s
....
672 705 85748.5210 91 1401 93349.3600 85043.7893 8.90% 0.0 9277s
704 729 85749.6040 94 1398 93349.3600 85043.7893 8.90% 0.0 38180s
728 769 85748.5210 96 1396 93349.3600 85043.7893 8.90% 0.0 38599s
....
4382 4569 86020.7519 459 1039 93349.3600 85043.7893 8.90% 0.0 77439s
-
Hi Jonathan,
A big difference between simplex and interior point methods is the ability to use well warm-starts. That is usually the reason behind simplex is usually used in the branch and bound nodes, since it is able to somehow use previous branches' solutions.
In the Method parameter, you can set the method you want to use for the root node. By default, Gurobi will likely use multiple methods between your CPUs. It seems like in your case, might be worth it setting to using only barrier.
Regarding the time spent in heuristics, you may want to change it with the Heuristics parameter.
1 -
Regarding question 2)
No, when solving an MIQP model, either you should use the barrier for all QP relaxations including root and node via setting Method=2 and NodeMethod=2, or all the QP relaxations will be solved by the simplex algorithm.
Regarding question 3)
It is hard to identify the main reason by just looking at the log. There might be because 1) barrier took a long time to solve a particular node QP relaxation or 2) a heuristic took a long time to finish. What happens if you set Heuristics=0?
Best regards,
Maliheh
1 -
Hi Maliheh,
Thanks for your answer. About question 3, I guess that a QP relaxation just could take excessive long time in the presence of numerical issues, in which case the node processing would be terminated early and identified as "postponed", is that right or there are another reasons? About heuristics, I am curious, is there a time limit for each heuristic process? Or, is it perform considering another termination criteria (in which case could be expensive in some cases)? Also, it can be possible that the heuristic return a non-basic solution and then a lot of time is spent to turn it to a basic solution? Finally, since the most of the solutions found in the model were through heuristics, turn off them (Heuristics=0) probably will lead to a completely different log where the indicated problem does not occur.
0 -
Thanks for your answer. About question 3, I guess that a QP relaxation just could take excessive long time in the presence of numerical issues, in which case the node processing would be terminated early and identified as "postponed", is that right or there are another reasons?
If Gurobi decides to postpone solving the relaxation of a particular node, we should see "postponed" in the "Obj" column of that particular node in the log. At least based on the log snippets you posted, I do not think this explains the long halt in the log file progress. The log file does not include enough information to determine the real reason for the lag. It can be because of node relaxations or heuristics taking too long or because of the tree search restart.
About heuristics, I am curious, is there a time limit for each heuristic process? Or, is it perform considering another termination criteria (in which case could be expensive in some cases)? Also, it can be possible that the heuristic return a non-basic solution and then a lot of time is spent to turn it to a basic solution?
Yes, there are strategies inside the solver that controls the heuristics' runtimes. The majority of heuristic algorithms embedded inside the optimizer are not exposed externally. The exceptions are NoRel and RINS heuristics. For these heuristics, there are parameters such as NoRelHeurTime, RINS, and SubMIPNodes where the user can impact the time spent on these particular heuristics.
The basic and non-basic solutions are relevant in the context of linear programming and not heuristic algorithms. The majority of heuristic algorithms in Gurobi use various strategies as simple as rounding or as complex as solving smaller sub-MIPS to make the current relaxed solution feasible.
Finally, since the most of the solutions found in the model were through heuristics, turn off them (Heuristics=0) probably will lead to a completely different log where the indicated problem does not occur.
The comment was just an attempt to see whether heuristics are responsible for the long lag in the log file or not. You are absolutely right that it can have a negative impact on the solver performance.
1
Please sign in to leave a comment.
Comments
4 comments