Branch and Bound

Branch and bound solves hard discrete problems by recursively splitting the search space and pruning branches that cannot beat the best solution found.

Divide and prune

Many optimization problems have exponentially many candidate solutions, making brute force hopeless. Branch and bound organizes the search as a tree. Branching splits the feasible region into subregions, for example by fixing an integer variable to 0 in one child and 1 in the other. Bounding computes, for each subregion, an optimistic bound on the best objective achievable within it, usually by solving an easy relaxation.

The pruning rule

The method keeps track of the best complete solution found so far, called the incumbent. If a subregion's optimistic bound is no better than the incumbent, then no solution in that subregion can improve on it, so the entire subregion is discarded without further exploration. This pruning is what makes branch and bound vastly faster than enumeration on typical instances, even though the worst case is still exponential.

• Relaxation quality: tighter bounds prune more, cutting the tree
• Branching variable choice: strong branching reduces tree size
• Node order: best-first finds good incumbents; depth-first saves memory
• A good early incumbent (from a heuristic) prunes aggressively

def branch_and_bound(relax, is_integral, branch, sense='min'):
    best = None; best_val = float('inf')
    stack = [relax()]                 # root relaxation
    while stack:
        node = stack.pop()
        if node is None or node.bound >= best_val:
            continue                  # infeasible or pruned
        if is_integral(node):
            if node.value < best_val:
                best_val, best = node.value, node.solution
        else:
            stack.extend(branch(node)) # split into children
    return best, best_val

Guarantees

Branch and bound is exact: given enough time it returns a provably optimal solution together with a certificate, namely the gap between the best incumbent and the best remaining bound. Stopping early yields a feasible solution plus a guaranteed optimality gap, which is often good enough in practice. It is the backbone of mixed-integer programming solvers, where it is combined with cutting planes to form branch and cut.