Understanding the best bound of the MIP

Answered

Magnus Mariegaard

• November 24, 2022 13:39

Hi quick question, in your description of best bound and gap you state that (for a min problem): "Somewhat less obvious is that, at any time during the branch-and-bound search we also have a valid lower bound, sometimes call the best bound. This bound is obtained by taking the minimum of the optimal objective values of all of the current leaf nodes.".

I am having trouble understanding if when you refer to the optimal objective values of the current leaf nodes, does this reffer to the optimal objective for the LP relaxation of the problem? If not and this is only for nodes that produce integer solutions how does this then differ from the upper bound found?

0

• 

  Jaromił Najman

  Gurobi Staff

  • November 25, 2022 13:39

  Hi Magnus,

  I am having trouble understanding if when you refer to the optimal objective values of the current leaf nodes, does this reffer to the optimal objective for the LP relaxation of the problem?

  Yes, this refers to the optimal objective values of the LP relaxation of all the current leaf nodes. We explicitly state "optimal objective values", because it is possible that a leaf node could have a sub-optimal status when using NodeMethod=2 (i.e., solving B&B nodes with Barrier).

  Best regards, 
  Jaromił

  1

Please sign in to leave a comment.