Branch and Bound - what to store

Question

I have read in more than one book (including Wolsey) that when implementing a branch and bound algorithm, one does not need to store the whole tree, just a list of active nodes (leaf nodes, for what I understand).

The thing is, I could not understand how to work out the new bounds after I branch, if I don't have the bounds of every ancestor.

Some clarification on that would be appreciated.

Answer 1

OK, let's work out an example. Let's say you're implementing a fairly naive integer program solver that tries to solve a binary integer program by solving its LP relaxation, and, if it doesn't get an integral solution, branches on some variable. Let's suppose you have a maximisation problem.

Let's consider what happens after exactly one branch. You solved the root subproblem, and suppose it gave you a fractional solution with objective value 10. Then you branched on a variable, giving you a left subproblem with optimal objective value 9 and a right subproblem with optimal objective value 8.

We got a global bound of 10 from the root subproblem. We also know that every integral solution lies in either the left subproblem or the right subproblem, and we know that the left subproblem has no solutions better than 9 and the right subproblem has no subproblems better than 8. Then there are no solutions better than 9 to the root subproblem, even though the root LP relaxation wasn't enough to tell us that.

In general, your best global bound is the worst bound any active subproblem. Fathomed subproblems are irrelevant since they can't contain a feasible solution with better objective value than your incumbent. Subproblems that have been branched are irrelevant because their bounds should be dominated by the weakest of their childrens' bounds.