Lesson 3

Let us now make branch-and-bound itself completely explicit. We use the one-share index-tracking problem and search through the binary decisions in the input order. If stock \(i\) is selected, the error changes by \[\Delta_{i}=|p_{i}-t_{i}|-t_{i}.\] The portfolio with no selected stocks is always feasible, so initially \[\operatorname{best}=\sum_{i} t_{i}.\]

At a node with next position \(i\), already spent money \(b\), and current error \(e\), first count this node as visited. If \(b>B\), stop. Otherwise compute the lower bound \[e+\sum_{j=i}^{n} \min(0,\Delta_{j}).\] If this bound is at least \(\operatorname{best}\), stop. If all stocks have been decided, set \(\operatorname{best}=e\) and stop. Otherwise first recurse to the branch where stock \(i\) is selected, and then to the branch where it is not selected.

The number of visited nodes tells us how much of the full recursion tree survived the bound.