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…