1
$\begingroup$

I am teaching myself branch and bound and keep coming across the term optimality gap. So I am looking at an example (shown in the image below) and would like to know if my analysis is correct. I think the arrows drawn in the example are misleading me but I have found a way for it to make sense to me and I would like to confirm that I am correct. Note the top value in the node circles are the local upper bound and the bottom value is the local lower bound.

enter image description here

So based on the image above, the following is my analysis:

  1. Starting at N1, no upper bound has been determined and the global lb at the root node is -13/2 (not shown on the diagram).

  2. After branching on the root node, the global ub remains unchanged but the now the global lb is given as the min(-13/3, -16/3) = -16/3. Min is used as this is a minimization problem.

  3. Ignoring the blue arrow and branching on N2, the global ub now becomes -3 due to a feasible optimal solution being found. Furthermore, since N5 is infeasible and no solution exists, the global lb is now given by the min(-3, -16/3) i.e. a comparison between the local lb of N4 and N3. Hence a global lb of -16/3.

  4. Now branching on N3, we get N6 and N7, however there is no solution associated with N7 as it is infeasible and the global lb is now -22/5 as this is the only active node left. Also the global ub remains as -3 as no new feasible solution is found.

  5. Lastly branching on N6, we get N8 and N9, the new global lb is given as the min(-4, -3) = -4. Since both are feasible solutions, the nodes are fathomed and the global ub is updated as a better feasible optimal solution is found.

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, this analysis is essentially correct, although you are conflating branching and processing a node. Branching creates two children but does not necessarily process them right away. Processing means solving the LP relaxation at that node.

You are processing the nodes as a breadth first search (BFS). The paper mentions DFS, which is depth first search, but that must be a typo because the global bounds instead match your BFS.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .