Introduction

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 — 2n2^{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.

Try It: Prune a Knapsack

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">A knapsack of capacity <b>10</b> and five items. The solver explores items in order of value-to-weight ratio, branching <b>take</b> vs <b>skip</b>. At each node it computes an optimistic bound; if that bound can't beat the best packing found so far, the whole subtree is <b>pruned</b> (red) and never entered.</p>
<div class="items" id="items"></div>
<div class="btns">
  <button id="solve" type="button">Solve (branch & bound)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Press Solve to watch the pruning.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 0/1 KNAPSACK by BRANCH AND BOUND.
// Items are sorted by value/weight. We branch take/skip on each item.
// Bound at a node = current value + greedy fractional fill of the remaining
// capacity using the not-yet-decided items. This bound is OPTIMISTIC (it can only over-estimate), so pruning a node whose bound <= best is always safe.
const CAP = 10;
// {n:name, w:weight, v:value}  -- sorted below by ratio v/w descending
let ITEMS = [
  { n: 'A', w: 2, v: 6 },
  { n: 'B', w: 4, v: 10 },
  { n: 'C', w: 3, v: 7 },
  { n: 'D', w: 5, v: 9 },
  { n: 'E', w: 1, v: 1 }
];
ITEMS.sort((a, b) => b.v / b.w - a.v / a.w);

function renderItems() {
  const el = document.getElementById('items'); el.innerHTML = '';
  ITEMS.forEach(it => {
    const d = document.createElement('div'); d.className = 'item';
    d.innerHTML = it.n + '<small>w' + it.w + ' / v' + it.v + '</small>';
    el.appendChild(d);
  });
}

// Optimistic bound: take whole items greedily, then a fraction of the next.
function bound(i, weight, value) {
  let b = value, w = weight, k = i;
  while (k < ITEMS.length && w + ITEMS[k].w <= CAP) { w += ITEMS[k].w; b += ITEMS[k].v; k++; }
  if (k < ITEMS.length) b += (CAP - w) * (ITEMS[k].v / ITEMS[k].w); // fractional piece
  return b;
}

function solve() {
  let best = 0, bestSet = [], visited = 0;
  const log = [];
  function rec(i, weight, value, taken, depth) {
    visited++;
    const indent = '  '.repeat(depth);
    // Prune: even the optimistic best down here can't beat the incumbent.
    const bnd = bound(i, weight, value);
    if (bnd <= best && best > 0) {
      log.push({ cls: 'pruned', text: fmt('%indent%x prune (bound %bnd% <= best %best%)', { indent: indent, bnd: bnd.toFixed(1), best: best }) });
      return;
    }
    if (i === ITEMS.length) {
      if (value > best) {
        best = value; bestSet = taken.slice();
        log.push({ cls: 'best', text: fmt('%indent%* leaf value %value%  <- new best {%taken%}', { indent: indent, value: value, taken: taken.join(',') }) });
      } else {
        log.push({ cls: 'dead', text: fmt('%indent%. leaf value %value%', { indent: indent, value: value }) });
      }
      return;
    }
    const it = ITEMS[i];
    // Branch 1: take the item (only if it fits).
    if (weight + it.w <= CAP) {
      log.push({ cls: 'node', text: fmt('%indent%take %n% (w%weight%%w% v%value%%v%)', { indent: indent, n: it.n, weight: weight, w: it.w, value: value, v: it.v }) });
      rec(i + 1, weight + it.w, value + it.v, taken.concat(it.n), depth + 1);
    }
    // Branch 2: skip the item.
    log.push({ cls: 'node', text: fmt('%indent%skip %n%', { indent: indent, n: it.n }) });
    rec(i + 1, weight, value, taken, depth + 1);
  }
  rec(0, 0, 0, [], 0);
  return { best, bestSet, visited, log, leaves: 1 << ITEMS.length };
}

function run() {
  const r = solve();
  document.getElementById('status').textContent =
    fmt('Optimum value %best% {%bestSet%}  -  visited %visited% nodes vs %leaves% brute-force leaves.', { best: r.best, bestSet: r.bestSet.join(','), visited: r.visited, leaves: r.leaves });
  const t = document.getElementById('tree'); t.innerHTML = '';
  r.log.forEach(l => {
    const s = document.createElement('span'); s.className = 'node ' + l.cls;
    s.textContent = l.text + '\n'; t.appendChild(s);
  });
  console.log('Branch-and-bound result:', 'best=' + r.best, 'set=' + r.bestSet.join(','), 'visited=' + r.visited);
}
function reset() {
  document.getElementById('tree').innerHTML = '';
  document.getElementById('status').textContent = 'Press Solve to watch the pruning.';
}
document.getElementById('solve').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', reset);
renderItems();
Result
Console

Press Solve and watch the count. Brute force would visit all 2n2^{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 2n2^{n}: the gap is the search you never had to do.

The Real Complexity

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 2n2^{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.

Where It Matters

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.

Conclusion

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 2n2^{n} possibilities into a handful of branches actually worth walking.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/branch-and-bound/Content licensed under CC BY-NC 4.0.