Skip to main content

MIP Performance based on simplex and barrier

Answered

Comments

4 comments

  • Michel Soares
    Thought Leader

    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
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    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
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    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
  • Jonathan Ayala Marcelo
    First Comment
    First Question

    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

Please sign in to leave a comment.