I am implementing a branch and bound algorithm for the knapsack program that is essentially identical to the one described here. I am trying to decide on the optimal data structure to store the set of candidate nodes.
It seems there are two natural choices: Either a kind of tree that represents the relationships between parent and child nodes, or a heap sorted by the LP relaxation values.
Suppose there are $n$ nodes in the candidate set (i.e. nodes that are not leaves and have not had their children explored). At each iteration, we
- Select the candidate node having the highest LP upper bound and generate child nodes by fixing $x_s = 0$ and $x_s = 1$ (where $s$ is the index of the "critical" item that takes a fractional value in the LP relaxation).
- If one of the child nodes yields a feasible, integral solution with a higher objective value than our best solution on hand, we inspect the remaining candidate nodes and "fathom" any for which the LP relaxation value is less than the new lower bound.
The heap has the advantage of reducing the time used in step 1 to $O(1)$ rather than $O(n)$. But since the heap doesn't encode any information about the parent-child relationships among nodes, identifying the nodes that we can fathom in step 2 is $O(n)$, because a fathomable node could conceivably be anywhere on the heap (right?), and then actually removing these keys from the heap costs $O(\log n)$ each.
From this analysis, it would appear that the better choice is to choose the tree data structure. Then the search step (step 1) costs $O(n)$, but then the fathoming step (step 2) is also $O(n)$ because each node is removed in unit time.
However, this is not what I see in other implementations: When I run branch-and-bound solvers like SCIP, the terminal message at each iteration says "1234 nodes on heap." This makes me think that they have somehow figured out a way to get the best of both worlds from a heap, i.e. selecting the branch node in unit time and completing the fathoms in $O(n)$ time. Is this possible? How?