long time after root relaxation before branch and bound

Answered

ce jekl

• March 18, 2022 15:51
• Edited

What does gurobi do after the root relaxation and before branch and bound?

0

• 

  Eli Towle

  Gurobi Staff

  • March 18, 2022 23:41

  Gurobi is likely performing degenerate simplex moves to improve the integrality of the relaxation solution. I would try setting the DegenMoves parameter to 0. From the DegenMoves documentation:

  The default setting generally works well, but there can be cases where an excessive amount of time is spent after the initial root relaxation has been solved but before the cut generation process or the root heuristics have started. If you see multiple 'Total elapsed time' messages in the log immediately after the root relaxation log, you may want to try setting this parameter to 0.

  0
• 

  ce jekl

  • March 19, 2022 18:28
  • Edited

  

  

  

  Thank you very much!

  Sorry, I don't quite understand the meaning of "integrality of the relaxation solution".

  1. Does it mean the number of integral variables in the relaxation solution or other things?
  2. Do you have any idea why this situation happens and a possible solution for that?
  3. Is there any reference to let me know how gurobi accomplish that?

  0
• 

  Eli Towle

  Gurobi Staff

  • March 24, 2022 03:51

  It is often the case that the LP relaxation has an optimal face, not just an optimal vertex. If Gurobi is spending a lot of time doing something between the root relaxation solve and setting up the branch-and-bound tree, this likely indicates that Gurobi is performing degenerate simplex moves to explore other vertices on this optimal face. One possible goal of this exploration is to find solutions in which more integer variables are at integer values. This 2018 presentation from Gurobi's VP of research and development discusses this topic in more detail.

  The maximum number of degenerate simplex moves that Gurobi performs is governed by the DegenMoves parameter. The default setting usually works well, but there are cases like yours where Gurobi spends large amounts of time between the root relaxation solve and the start of the branch-and-bound process. If you set DegenMoves to 0, I expect this behavior will disappear.

  0

Please sign in to leave a comment.