Exact

Branch and Bound
Aliasbranch_bound
TypeExact
ComplexityExponential worst-case; effective pruning often makes it practical for small instances

Description

Systematic enumeration of candidate tours that prunes any branch whose lower-bound cost already exceeds the best complete tour found so far. Explores the search tree depth-first, backtracking whenever it can prove no improvement is possible below the current node.

Do not use on more than ~20 cities — worst-case complexity is factorial.

procedure BranchAndBound(cities):
    best ← nearest_neighbor(cities)   // initial upper bound
    queue ← [partial tour starting at city 0]
    while queue not empty:
        node ← pop_most_promising(queue)
        if lower_bound(node) ≥ length(best):
            continue                   // prune branch
        if node is a complete tour:
            best ← node
        else:
            for each unvisited city c:
                queue.push(extend(node, c))
    return best

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