What Is Branch and Bound? The Optimization Algorithm Explained

You have a knapsack that holds 10 kg. You have five items. You want to maximize value. The brute-force approach tries every combination: 2^5 = 32 possibilities, fine. Now scale to 50 items. That's over a quadrillion combinations, and your laptop will still be chewing on iteration number 73 when the sun goes red giant.

The branch and bound algorithm solves this class of problem by being selectively lazy. It never explores a branch of the search tree when it can prove that branch cannot beat the best solution already found. You still search, but you throw away huge swaths of work before doing it.

That is the whole idea. A principled decision to not bother. The rest is just details about how to compute those proofs efficiently.

You Are Building a Tree (And Then Cutting Most of It Down)

Branch and bound is a tree search. Each node represents a partial decision. For the knapsack, the root node is "no items chosen yet." Its two children are "item 1 included" and "item 1 excluded." Each of those spawns two more children for item 2, and so on until every item has been decided.

That tree has 2^n leaves. You cannot visit all of them. The question is which subtrees you can safely skip.

The branching step just creates child nodes. The bounding step is where the algorithm earns its name.

At each node, before recursing into it, you compute an upper bound on the best total value any complete solution in that subtree could possibly achieve. If that upper bound is no better than the best complete solution you already have, you discard the entire subtree. Every node under it, every combination it contains, pruned in a single comparison.

This is the part that separates "I wrote a DFS" from "I wrote an efficient solver." You are not just exploring less of the tree. You are proving that the unexplored parts cannot possibly matter.

The Bound Comes from Relaxing the Problem

The tricky part is computing a tight upper bound cheaply. Tight means it cuts aggressively. Cheap means computing it does not cost more than just exploring the branch.

For the 0/1 knapsack, the standard trick is the fractional relaxation. In the real problem you can only take whole items. In the relaxed version you can take a fraction of one, like half a gold bar. Is that cheating? Absolutely. That is the point.

A fractional solution is always at least as good as any integer solution, which makes it a valid upper bound on what the integer branch can achieve.

Computing the fractional optimum takes O(n log n) to sort by value density, then one linear pass. At any node, you start with the items already committed and greedily fill the remaining capacity, fractionally if needed. The result is your upper bound.

def upper_bound(items, index, capacity, current_value):
    remaining = capacity
    bound = current_value
    for i in range(index, len(items)):
        v, w = items[i]
        if w <= remaining:
            remaining -= w
            bound += v
        else:
            bound += v * (remaining / w)
            break
    return bound

If upper_bound(...) for a node comes back at 42 and your best complete solution so far is 45, you skip that node entirely. No argument. No second look. Gone.

Four Items, Ten Kilograms

Four items, capacity 10 kg:

Item	Weight	Value	Value/kg
A	2	6	3.0
B	2	5	2.5
C	6	8	1.33
D	5	9	1.8

Sorted by value density: A, B, D, C.

Start at the root: no items chosen, weight 0, value 0. The upper bound is the fractional knapsack solution: take A (2 kg, +6), take B (2 kg, +5), take D (5 kg, +9), 1 kg of C (+1.33). Bound = 21.33.

Branch into "include A" and "exclude A."

At "include A" (weight 2, value 6), recompute bound: take B, D, 1 kg C. Bound = 21.33 still. Worth exploring.

At "exclude A," bound is lower since we lose A entirely. Still potentially interesting.

Continue branching. When you reach a node where the bound drops to 16 and you have already found a complete solution worth 20, you cut the whole subtree. You never touch any of the combinations hiding under that node. It is the algorithmic equivalent of seeing a 1-star Yelp review and closing the tab.

The full implementation:

def knapsack_branch_and_bound(weights, values, capacity):
    n = len(weights)
    items = sorted(zip(values, weights), key=lambda x: x[0] / x[1], reverse=True)
    best = [0]

    def upper_bound(index, remaining_capacity, current_value):
        bound = current_value
        for i in range(index, n):
            v, w = items[i]
            if w <= remaining_capacity:
                remaining_capacity -= w
                bound += v
            else:
                bound += v * (remaining_capacity / w)
                break
        return bound

    def branch(index, remaining_capacity, current_value):
        if current_value > best[0]:
            best[0] = current_value

        if index >= n:
            return

        if upper_bound(index, remaining_capacity, current_value) <= best[0]:
            return

        v, w = items[index]

        if w <= remaining_capacity:
            branch(index + 1, remaining_capacity - w, current_value + v)

        branch(index + 1, remaining_capacity, current_value)

    branch(0, capacity, 0)
    return best[0]

Notice the single key line: if the upper bound cannot beat best[0], return immediately. Everything else is standard DFS. The entire cleverness of the algorithm is in that one comparison.

Backtracking Prunes for Feasibility. Branch and Bound Prunes for Optimality.

Both algorithms explore a tree and cut branches early. The difference is what triggers the cut.

Backtracking abandons a branch when it violates a constraint. Branch and bound abandons a branch when, even if it produces a valid solution, that solution cannot beat what you already have.

Backtracking is for constraint satisfaction: you want any valid solution, or all of them. Branch and bound is for optimization: you want the best valid solution. You can apply both simultaneously, pruning infeasible paths on the way down and suboptimal paths using bounds.

N-queens uses pure backtracking. The moment a queen threatens another, you abandon that branch. No values to optimize, just rules to satisfy.

Knapsack can use both: abandon branches where weight exceeds capacity (feasibility) and abandon branches where the upper bound is too low (optimality). They stack. The more reasons you have to quit early, the faster you go.

When Branch and Bound Beats DP

Dynamic programming is the other tool for these optimization problems. For the 0/1 knapsack, DP gives you O(n × W) time and space, where W is the capacity. Excellent when W is small.

When W is huge, say 10^9, the DP table is 10^9 entries long. You are not fitting that in RAM. You are not fitting that anywhere. For large-capacity or high-dimensional problems where the DP state space explodes, branch and bound is often the more practical choice.

DP also requires optimal substructure. Branch and bound does not. It works on any problem where you can compute a useful bound, regardless of whether subproblems overlap in the right way.

In practice, industrial solvers like CPLEX and Gurobi combine both: LP relaxation at each node to compute bounds, cutting planes to tighten the relaxation, and a full branch-and-bound search over the resulting tree. They are doing the same thing you just read, just with considerably more engineering.

What Pruning Actually Buys You

Worst-case time is still O(2^n). If your bounds are garbage, you visit the whole tree and the algorithm is just slow DFS with extra steps.

In practice, pruning is often dramatic. A tight upper bound eliminates large subtrees at shallow depths. For the knapsack, with items sorted by density and the fractional relaxation as the bound, effective pruning routinely reduces the explored space by orders of magnitude on random instances. You go from "heat death of the universe" to "done in milliseconds" with the same problem.

Space is O(n) if you do DFS. The recursion stack holds at most one path from root to leaf, which has depth n. BFS-based variants must store all live nodes simultaneously and can require O(2^n) space in the worst case. Do not do BFS unless you enjoy watching memory get eaten.

For NP-hard problems like TSP, branch and bound still scales poorly past 40-50 nodes. Practical solvers use approximations, heuristics, or hybrid methods beyond that point. Branch and bound proves optimality for small and medium instances, which is exactly what makes it valuable when you need a certificate, not just a good answer.

Does This Show Up in Coding Interviews?

Rarely, and almost never by name.

FAANG interviews almost never ask for branch and bound directly. The expectation for an optimization problem is usually a greedy or DP solution. If you encounter a 0/1 knapsack variant, reach for DP first. If you open with "I'm going to apply branch and bound with LP relaxation," the interviewer will look up from their notes.

Where branch and bound does appear:

Senior or specialist roles at companies doing operations research (logistics, scheduling, resource allocation)
Systems-level design questions about how solvers work
Academic and competitive programming contexts
Understanding why some problems are hard and what "exponential in the worst case, tractable in practice" actually means

Understanding branch and bound sharpens your instincts around NP-completeness, pruning strategies, and the relationship between relaxation and exact algorithms. That surfaces in how you discuss complexity and defend algorithmic choices under pressure. Saying "the brute-force approach is 2^n but we can prune aggressively by computing an upper bound at each node" is a real thing you might say in a senior-level conversation.

If you want to practice explaining those tradeoffs out loud, SpaceComplexity runs voice-based mock interviews with structured feedback on exactly that: how well you reason through complexity and defend choices to an interviewer in real time.