Interpretation best bound NoRel heuristic

Answered

Anne-Kett Bassing

• July 14, 2022 11:07
• Edited

Hello! 

I've improved the solving time of my model significantly by spending more time in the NoRel Heuristic. For all the instances I've tested so far the optimal objective function value has been equal to the best bound given in the following line:

Elapsed time for NoRel heuristic: 189s (best bound 120)

I have a minimization problem. Could someone explain to me how the best bound is computed and how I can interpret it? I guess that my optimal solution will not always be equal to the best bound?

 

Also is there a rule of thumb how much time I should spend on this heuristic?

Thank you!

1

• 

  Maliheh Aramon

  Gurobi Staff

  • August 02, 2022 03:46

  Hi Anne-Kett, 

  You can think of the best bound in the NoRel heuristic as a global valid bound obtained by relaxing the constraints as opposed to the usual way of relaxing the integrality constraints. This bound is not directly used in the NoRel heuristic and you are right that it is just a coincidence that the optimal solution for the models you tested happens to be equal to the best bound obtained in the NoRel heuristic. 

  There is no general rule for the time spent in the NoRel heuristic and the time is problem dependent and should be determined experimentally.  For most of the problems, we will eventually reach a time where spending more time in the NoRel heuristic does not lead to finding a better feasible solution. 

  Best regards,

  Maliheh

  0

Please sign in to leave a comment.