Skip to main content

How does NodeMethod work?

Answered

Comments

6 comments

  • Fikri Kucuksayacigil
    Gurobi-versary
    Collaborator
    Curious

    Hi again,

    I have just the checked definition of NodeMethod, and it seems that only one of dual simplex, primal simplex, or barrier is applied in B&B nodes. When I do not have NodeMethod = 2 and Crossover = 0, it chooses one of them automatically, and apparently this was much faster. When I added NodeMethod = 2 and Crossover = 0, I enforced that the algorithm should use only barrier in B&B nodes, which is too slow in my case.

    Can somebody confirm that I am right? If I am right, then what does Gurobi choose among primal simplex, dual simplex, and barrier when the setting is automatic?

    Thank you

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Fikri,

    You are correct. When setting NodeMethod=2, Gurobi will use the Barrier method in every node of the B&B tree. This is in most cases way slower than using one of the simplex methods because Barrier cannot utilize warm start information. For the default setting, Gurobi will choose one of the algorithms, most often the dual Simplex.

    In order to avoid Crossover after the root node it is required to also force NodeMethod=2. This is because Gurobi will need a valid basis anyway when starting the B&B algorithm in order to benefit from warm starts. Thus, Crossover is performed.

    It seems like your model may suffer from numerical issues. The very large objective values, the sub-optimal termination of the root node Barrier, together with the many postponed nodes when using NodeMethod=2 are all indicators for numerical trouble. Did you had the chance to look at our Guidelines for Numerical Issues? Proper scaling often makes the difference between a solvable and an unsolvable model.

    Best regards,
    Jaromił

    0
  • Fikri Kucuksayacigil
    Gurobi-versary
    Collaborator
    Curious

    Hi Jaromil,

    Thank you so much for your answer. It is getting clearer, but I need more guidance with the following questions. I am sorry if they are repetitive of the previous ones.

    1) NodeMethod only affects the nodes after the root node, right? It has no effect on the root node.

    2) If NodeMethod = 2, Gurobi relaxes MIP in a relevant leaf node, solves it with barrier, and then does crossover in order to get a basic solution. If NodeMethod = -1, it chooses an algorithm automatically (generally dual simplex as you said), and then directly solves with dual simplex to get a basic solution. Is this correct? If correct, then why is dual simplex so much faster than barrier? Generally, barrier is a faster solution method.

    3) So far, my questions have been about leaf nodes after the root node. As for the root node, can I just solve with barrier without any crossover? You are saying above that "Gurobi will need a valid basis anyway when starting the B&B algorithm in order to benefit from warm starts.". Does it mean that I can not avoid crossover for the root relaxation? If I can not avoid, then what does Crossover = 0 do?

    What I am eventually trying to do is as follows:

    • Use only barrier without crossover for the root relaxation
    • Start B&B tree
    • Use automatic setting (dual simplex) for the relaxation of leaf nodes

    What parameter setting should I use for this one? I once tried Method = 2 along with Crossover = 0 in order to avoid crossover for the root relaxation, but it still did crossover.

    Could you please clarify these points for me?

    Kind regards

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Fikri,

    1) NodeMethod only affects the nodes after the root node, right? It has no effect on the root node.

    Correct.

    2) If NodeMethod = 2, Gurobi relaxes MIP in a relevant leaf node, solves it with barrier, and then does crossover in order to get a basic solution. If NodeMethod = -1, it chooses an algorithm automatically (generally dual simplex as you said), and then directly solves with dual simplex to get a basic solution. Is this correct? If correct, then why is dual simplex so much faster than barrier? Generally, barrier is a faster solution method.

    If NodeMethod is set to 2, then Gurobi solves each B&B node with Barrier and Crossover unless Crossover=0.
    Correct, if NodeMethod=-1, then Gurobi usually picks dual Simplex.
    Using a Simplex algorithm in the B&B tree is usually much faster than Barrier, because of the ability to use warm start. In a warm start, the Simplex algorithm can re-use old Basis information to skip phase 1 and directly proceed with phase 2. Often enough, it is the case that phase 2 needs only a few iterations, because the previous solution point is not far away from the new one such that the Simplex algorithm only has to wander across a few edges of the polyhedron. In contrast, there is currently no methodology to make use of warm start for the Barrier algorithm. This results in Barrier being forced to always compute a valid starting point first. Moreover, Simplex algorithms are often faster than Barrier for small - medium and sometimes even on large models.

    3) So far, my questions have been about leaf nodes after the root node. As for the root node, can I just solve with barrier without any crossover? You are saying above that "Gurobi will need a valid basis anyway when starting the B&B algorithm in order to benefit from warm starts.". Does it mean that I can not avoid crossover for the root relaxation? If I can not avoid, then what does Crossover = 0 do?

    You can only solve the root node without Crossover if you also set NodeMethod=2. This is because Gurobi would like to take advantage of warm start for the B&B nodes and requires a basic solution and thus, will use Crossover anyway to get one if NodeMethod=-1. The only way to avoid Crossover in the root node is to additionally set NodeMethod=2. However, this may then hurt the overall performance because one usually does not want to run Barrier in leaf nodes.

    What I am eventually trying to do is as follows:

    • Use only barrier without crossover for the root relaxation
    • Start B&B tree
    • Use automatic setting (dual simplex) for the relaxation of leaf nodes

    What parameter setting should I use for this one? I once tried Method = 2 along with Crossover = 0 in order to avoid crossover for the root relaxation, but it still did crossover.

    Could you please clarify these points for me?

    Concluding, if you want to use Barrier for the root node and Simplex for leaf nodes then there is no way to avoid Crossover.

    Best regards,
    Jaromił

    0
  • Fikri Kucuksayacigil
    Gurobi-versary
    Collaborator
    Curious

    Hi Jaromil,

    I forgot to thank you. Everything is very clear now. I have some issues in making the optimization faster though. I will open another issue for that.

    Kind regards

    0
  • Alison Cozad
    Gurobi Staff Gurobi Staff

    For reference, here is the link to the separate post: How to make the search over B&B tree faster? – Gurobi Support Portal

    0

Please sign in to leave a comment.