Exact
Branch and Bound
| Alias | branch_bound |
| Type | Exact |
| Complexity | Exponential 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.
Usage
teeline solve branch_bound -i ./data/discopt/tsp_5_1.tsp
teeline solve branch_bound -i ./data/discopt/tsp_5_1.tsp --verbose