Skip to content

Branch and Bound

A formal search method — instantiates Search Space Pruning

Discards an entire region of a search tree the moment a bound proves it cannot hold a better solution than the best one already found — narrowing the search while provably keeping the optimum.

Branch and Bound is the pruning method that can throw away vast swaths of a search space with a guarantee it did not throw away the best answer. It works by branching the space into subregions and, for each one, computing a bound — an optimistic estimate of the best score anything in that region could possibly reach. If that optimistic bound is already worse than the best complete solution found so far (the incumbent), the whole region is provably dominated and can be dropped unexplored. That is the move no other sibling here makes: it prunes by proof rather than by heuristic, filter, or judgment, so the narrowing is exact — the optimum survives every cut. Its power and its fragility both live in the bound: the tighter and more honestly optimistic it is, the more it prunes; the moment it lies, the guarantee is gone.

Example

A logistics team must assign 12 delivery routes to 12 drivers to minimize total drive time — over 479 million possible assignments, far too many to score one by one. Branch and Bound frames it as a tree: each level fixes one more driver-to-route pairing. At each partial assignment it computes a bound by relaxing the problem — allowing fractional assignments — which gives a total that no full assignment completing that branch could ever beat. Early on it finds one decent complete assignment (≈41 hours) as the incumbent. From then on, any partial branch whose relaxed bound already exceeds 41 hours is dropped whole, taking millions of leaf assignments with it. As better incumbents appear (≈38 hours, then ≈36), the pruning tightens and more of the tree collapses.

The result is the proven minimum, reached after exploring a tiny fraction of the space — and, crucially, the team can say with certainty that no discarded branch hid a better schedule. That certificate of optimality is exactly what a heuristic screen cannot provide.

How it works

  • Branch — split the space into disjoint subregions by fixing one more decision, so every candidate lives in exactly one leaf.
  • Bound — for each subregion, compute an optimistic bound (often via a relaxation, e.g. dropping integrality) on the best objective any candidate inside it could achieve.
  • Compare to the incumbent — hold the best complete solution found so far.
  • Prune by proof — if a region's optimistic bound is no better than the incumbent, discard the entire region; it cannot contain the optimum.

The discipline is that the bound must be admissible — never more pessimistic than the truth — or a discarded region might have held the answer. Everything else is search order.

Tuning parameters

  • Bound tightness — a looser bound is cheap to compute but prunes little; a tighter relaxation prunes aggressively but costs more per node. The trade is compute-per-node against nodes-explored.
  • Branching order — which decision to split on next; a good order finds strong incumbents early, which makes later bounds prune harder.
  • Incumbent seeding — starting from a good feasible solution (from a heuristic) raises the pruning bar immediately, collapsing the tree faster.
  • Exploration strategy — best-first finds the optimum with fewest nodes but hoards memory; depth-first is lean but may chase weak branches.
  • Optimality gap tolerance — accepting a solution provably within, say, 2% of optimal lets you stop early and prune far more.

When it helps, and when it misleads

Its strength is unique among the siblings: it prunes an exponential space while issuing a certificate that the optimum was preserved. When a provably-best (or provably-near-best) answer matters and a valid bound exists, nothing else here offers the same guarantee.

It misleads when the bound is weak or dishonest. A loose relaxation prunes almost nothing and the method degrades to near-exhaustive search — still exponential in the worst case. The classic misuse is swapping the real bound for a heuristic estimate that is not guaranteed optimistic, to make it run faster; the moment the bound stops being admissible, the method can silently discard the region containing the best solution and still report a confident "optimum."[1] The guard is to prove the bound admissible before trusting the certificate, and to treat any "bound" that is really just a guess as converting this method into an ordinary heuristic search with none of its guarantees.

How it implements the components

  • search_space_definition — the branching scheme is an explicit, exhaustive tree over the candidate space; every option occupies exactly one leaf.
  • dominance_check — the bound is a formal dominance proof: it shows an entire region is dominated by the incumbent and so cannot win.
  • pruning_rule — the elimination condition is exact and hard: discard a region iff its optimistic bound is no better than the incumbent.

It does not screen candidates against hard requirements — that is Constraint Filtering — nor preserve diversity in the surviving set (Shortlisting), nor audit its own exclusions (Sample Audit of Exclusions). Its guarantee makes those largely unnecessary within its scope, but only where a valid bound exists.

  • Instantiates: Search Space Pruning — Branch and Bound is the formal, optimality-preserving end of the archetype's spectrum.
  • Sibling mechanisms: Dominated-Option Removal · Beam Search · Constraint Filtering · Decision Tree Pruning · Eligibility Screening · Negative Keyword Filter · Red-Flag Screen · Safety or Compliance Exclusion · Sample Audit of Exclusions · Shortlisting · Triage Filter

Notes

Branch and Bound needs a well-defined objective and a computable bound; when the objective is fuzzy, multi-criteria, or the space cannot be relaxed, its guarantee evaporates and a heuristic sibling like Beam Search or a judgment-based screen is the honest choice. Its optimality certificate is only as sound as the bound's admissibility — a proof, not a vibe.

References

[1] A bound (or heuristic) is admissible when it never rules out a solution that could actually be optimal — it errs only on the optimistic side. Admissibility is exactly the property that lets A*-style search and branch and bound prune safely; drop it and pruning is no longer proof-preserving. ↩