Exact· v2.0.0
▶ Open interactive explainer →Branch and Bound
| Alias | branch_bound |
| Type | Exact |
| Complexity | Exponential worst-case; effective pruning often makes it practical for small instances |
| Benchmarks | published results ↓ |
Description
Exact depth-first enumeration of candidate tours. At each partial tour it sorts the unvisited cities by a lower bound — the cost so far, plus the edge to the next city, plus a minimum spanning tree over the start city and every remaining unvisited city — and prunes any branch whose bound cannot beat the best complete tour found so far. A nearest-neighbour tour (or the pipeline’s warm-start tour) seeds that upper bound.
Every unvisited city is always a candidate. --n_nearest is a heuristic option used by other
solvers and is ignored here: restricting the candidate set would silently turn an exact
solver into a beam search.
Do not use on more than 24 cities. The dispatcher rejects larger inputs with an error rather than letting an exponential search run until the caller gives up.
procedure BranchAndBound(cities):
best ← nearest_neighbor(cities) // or the pipeline warm-start
dfs(path = [city0], unvisited = rest, cost = 0)
return best
procedure dfs(path, unvisited, cost):
if unvisited is empty:
best ← min(best, cost + d(last, city0))
return
mst ← minimum_spanning_tree({city0} ∪ unvisited)
for c in sort_by(cost + d(last, c) + mst):
if cost + d(last, c) + mst ≥ length(best):
break
dfs(path + [c], unvisited \ {c}, cost + d(last, c))
Usage
teeline solve branch_bound -i ./data/discopt/tsp_5_1.tsp
teeline solve branch_bound -i ./data/discopt/tsp_5_1.tsp --verbose
References
Changelog
| Version | Date | Change |
|---|---|---|
| 2.0.0 | 22 Nov 2026 | Exact by default: removed the n_nearest candidate restriction that made the default a beam search, and added the 24-city exact-input guard. --n_nearest is now ignored. Tier A returns the published optima — burma14 3323, gr17 2085, ulysses16 6859 — instead of 3651 / 2187 / 6909. |
Benchmarks
Loading published results…