Branch and bound

An NP-hard problem has no known fast method for every input, but most inputs are not the worst case. Branch and bound searches every possible answer in principle, and skips whole groups of answers that provably cannot win. It always finds the best answer; how long it takes depends on how close its estimates are to the true values.

Search with a bound

RECR-5 searched a tree of choices and cut branches early. For an optimisation problem (here a maximum) the tree is the same: each node fixes a few more choices (take this item or not), and the leaves are complete answers. Two numbers drive the search:

• best: the value of the best complete answer found so far. Every answer found is a real one, so the best answer is at least this.
• bound(node): a number that no complete answer below this node can beat. It is an optimistic estimate, worked out quickly.

That is the whole method. Its correctness rests on one property of the bound: it must never be too small. A bound that is sometimes too small can throw away the best answer. A bound that is too large is safe, only slower.

def branch_and_bound(root, children, bound, value, complete):
    best = None
    stack = [root]                       # depth-first
    while stack:
        node = stack.pop()
        if complete(node):
            if best is None or value(node) > best:
                best = value(node)
            continue
        if best is not None and bound(node) <= best:
            continue                     # pruned: no answer below can win
        stack.extend(children(node))
    return best

Why the bound is safe

For the 0/1 knapsack, sort the items by value per kilogram, best first. At a node, the items before position k are decided and room kilograms are left. The bound fills the room with the undecided items in that order, and when the next item no longer fits, takes the fraction of it that fills the room exactly.

Why no real packing can beat it. Any real packing below the node uses whole undecided items within the room. That is also allowed in the fractional problem, where items may be cut. GRDY-1 proved that for the fractional problem, filling by best value per kilogram is optimal (an exchange argument). So the fractional value is at least the value of every whole-item packing: the bound is never too small. Round it down, since real values are whole numbers.

Step through the figure. The four items are sorted by value per kilogram; the tags are the bounds. Then switch to the weaker bound, which adds up all the undecided values whatever they weigh. It is also safe, but it prunes far less.

Which node next

• Depth first (a stack, or recursion), taking items before leaving them: it reaches complete answers quickly, so best becomes useful early, and it needs memory only for one path.
• Best first: keep the open nodes in a heap (HEAP-4) by bound, and always expand the one with the highest bound. It never expands a node whose bound is below the final answer, so it visits the fewest nodes, but the heap can grow very large.
• A good start: setting best to a greedy answer before the search (GRDY-5) lets pruning begin at the root.

How fast it is

In the worst case, branch and bound visits exponentially many nodes: the problem is NP-hard, and some inputs defeat any known bound. In practice the bound decides everything. With items whose values have little to do with their weights, a hundred items take under a thousand nodes. When every item has almost the same value per kilogram, many branches have bounds just above the best, and the search grows; the practice tests include one such case of 60 items that needs about 5,600 nodes. A weak bound is slower on every test: on the same tests it passes two million nodes without finishing.

The work per node matters too. The fractional bound costs O(n) to work out; prefix sums of the sorted weights and values plus a binary search (BSRC) bring it to O(log n).

Beyond the knapsack

• Travelling salesman: a cheapest spanning tree of the cities not yet visited (SPAN) gives a bound for the rest of the tour; sharper bounds use “one-trees” and penalties on vertex degrees.
• Integer programming: many problems can be written as a linear program (straight-line constraints and a straight-line goal) whose variables must be whole numbers. Dropping the whole-number rule gives a problem solvable in polynomial time, and its answer is a bound, just as cutting items was. Solvers branch on a variable with a fractional value. SciPy’s scipy.optimize.milp and OR-Tools do this, adding extra constraints (“cuts”) that bring the bound closer to the best answer.
• Games: alpha-beta pruning in chess programs is branch and bound for a game tree.

Now try HARD-P3, The most valuable load.