Branch and Bound

You have a knapsack that holds 10 kilograms and a pile of items, each with a weight and a value. Which subset fits and is worth the most? This is the knapsack problem, and it is NP-hard: nobody knows a method that stays fast as the item count grows, and the only sure way is, in the worst case, to consider every subset — $2^{n}$ of them.

And yet solvers crack knapsacks with hundreds of items in the blink of an eye. Airlines, factories and delivery networks solve far nastier versions every day. How, if the problem is intractable?

The trick is branch and bound. You still organize the search as a giant tree of choices — take this item, or leave it — but you never walk the whole tree. At each branch you compute a quick bound: the best you could possibly achieve down that path. If that optimistic best can't beat a solution you already have, you prune the entire subtree, unexplored. Worst case it is still exponential. In practice, it makes the impossible routine.

Here is a small knapsack: a capacity and a handful of items, each with a weight and a value. The solver explores items one by one — take it (left) or skip it (right) — building a binary tree of decisions.

<p class="hint">{{hint}}</p>
<div class="items" id="items"></div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="tree" id="tree"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.items { display: flex; gap: 6px; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.item { background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; border-radius: 8px;
        padding: .35rem .55rem; font-size: .82rem; font-weight: 600; }
.item small { display: block; font-weight: 400; color: #51606e; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #0a7d33; }
.tree { font: 12px ui-monospace, monospace; white-space: pre; line-height: 1.5; overflow-x: auto;
        border-top: 1px solid #e1e6ea; padding-top: .5rem; }
.node { display: inline; }
.node.best { color: #0a7d33; font-weight: 700; }
.node.pruned { color: #c92f3c; }
.node.dead { color: #9aa3ab; }

// Code not found

Press Solve and watch the count. Brute force would visit all $2^{n}$ leaves. Branch and bound computes, at every node, an optimistic upper bound (fill the remaining capacity greedily, even allowing a fractional item). The moment that bound falls at or below the best complete packing found so far, the whole subtree is pruned — colored red and never entered. Compare the nodes visited against $2^{n}$: the gap is the search you never had to do.

Branch and bound is an exact method — when it stops, the answer is provably optimal, not an approximation. Here is what makes it tick:

• The problem is NP-hard. Knapsack (the optimization version) is NP-hard, and its decision form is NP-complete. No polynomial-time algorithm is known, and finding one would settle P vs NP.
• Worst case is still exponential. If the bound never prunes anything, branch and bound degenerates into full brute force over $2^{n}$ leaves. The technique gives no asymptotic guarantee — it is a constant-factor-in-practice win, not a complexity-class breakthrough.
• Everything rides on the bound. A valid bound must be optimistic (never underestimate what a branch could yield) so pruning stays safe, yet tight enough to cut early. For knapsack, the classic bound is the fractional (greedy) relaxation — solvable in an instant and never pessimistic.
• It pairs with good ordering. Exploring promising branches first (here, best value-to-weight ratio) raises the incumbent best quickly, which makes later bounds prune harder.

Branch and bound was named by Ailsa Land and Alison Doig in 1960 for integer programming. It does not make NP-hard problems easy; it makes typical instances tractable by refusing to look where the answer provably cannot be.

Branch and bound (and its cousin branch-and-cut) is the workhorse behind exact combinatorial optimization:

• Integer programming: every industrial MILP solver — CPLEX, Gurobi, SCIP — is a branch-and-bound engine wrapped in clever bounds and cutting planes.
• Traveling salesman & routing: provably shortest tours and vehicle routes come from branch and bound over edge choices. See routes.
• Scheduling and assignment: timetables, crew rosters and machine schedules are solved exactly by branching on decisions and bounding the rest.
• Knapsack-shaped budgeting: capital allocation, cargo loading and ad selection are all "pick the best subset under a limit."

Wherever a problem is NP-hard but the answer truly has to be optimal, branch and bound is usually how it is done — the same idea also underpins exact solvers for graph coloring and SAT.

Branch and bound is a quiet kind of genius. It accepts that NP-hard problems may have no shortcut, then wins anyway by being ruthlessly lazy: it refuses to explore any branch it can prove will never hold the answer. The exponential tree is still there — branch and bound just never walks most of it.

So the next time a solver returns the provably best schedule or the cheapest route in seconds, remember it is not magic and it is not a fast algorithm in the P vs NP sense. It is one good optimistic bound, applied relentlessly, turning a forest of $2^{n}$ possibilities into a handful of branches actually worth walking.