7
$\begingroup$

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

  1. 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).
  2. 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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Note that this is a toy example, in real life 1) one does not solve a knapsack problem with a branch-and-bound algorithm 2) in a branch-and-bound, the cost of computing the bound is usually significantly greater than the time to manage the nodes, so its not very critical $\endgroup$
    – fontanf
    Mar 7, 2022 at 15:33
  • $\begingroup$ @fontanf I guess "toy example" is a relative term. The problem I am actually working on is a nonlinear integer program whose objective function is bounded from above by the value of a certain knapsack problem. I have better algorithms for my problem, but I am using a branch-and-bound routine as a benchmark, and I figured I would write my question here in terms of the basic knapsack problem, which is of more general interest. In the knapsack problem (unlike general IPs) the LP relaxation at each node can be solved in linear time, so IMO tree management is an important issue. $\endgroup$
    – Max
    Mar 8, 2022 at 0:15
  • $\begingroup$ Ok, that makes sense $\endgroup$
    – fontanf
    Mar 8, 2022 at 5:56
  • $\begingroup$ Fathoms or pruning only saves space rather than time, as far as I know. So I think you could just prune when the heap is full. $\endgroup$
    – xd y
    Mar 9, 2022 at 11:46

1 Answer 1

Reset to default
4
$\begingroup$

One approach is to not "fathom" them at the time we replace our best candidate. Rather, as things get naturally pulled from the heap (because they are the min/max heap root), we then toss and repull if said best is unusable. This avoids the $O(n)$ search.

Also, for a large heap change, it is faster to remove all the nodes and then do a single "reheapify" operation at the end. Don't do the child tree re-org after each deletion.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. The "toss and repull" method sounds quite practical. However, if I have understood correctly, I believe it is still $O(n)$ in the worst-case, because there could be $n-1$ fathomed nodes above the true branch node in the heap. Similarly, I think "reheapify" is going to be equivalent to my "tree" idea in the end, because emptying and reheapifying will cost $O(n)$ just like searching through the tree. I guess there is no way to get the time for a whole iteration below $O(n)$, huh? $\endgroup$
    – Max
    Mar 7, 2022 at 4:42
  • $\begingroup$ If, as you mentioned in the question, you follow a best first strategy, you might not need to fathom a lot of nodes anyway $\endgroup$
    – fontanf
    Mar 8, 2022 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.