Look-Ahead and Degree-Aware Branch-and-Bound for the Symmetric Traveling Salesman Problem: Algorithm, Complexity, and the Decisive Role of the Lower Bound
9/28/2026
Author: Pemson Pereira
Technical report — September 2026
Abstract
We analyse LDA-B&B, a branch-and-bound (B&B) solver for the symmetric traveling salesman problem (TSP) that combines a multi-start nearest-neighbour and 2-opt incumbent, one-step look-ahead and regret-based branch ordering, and a residual minimum-spanning-tree (MST) lower bound. We (i) state the algorithm formally and prove that pruning is safe and that the search is exact when it terminates; (ii) derive its time and space complexity, including a discrepancy between the documented and the implemented cost of the construction phase; (iii) report an implementation defect in the MST routine that silently prunes the root node and causes the solver to return its heuristic tour while claiming a proof of optimality; and (iv) evaluate a corrected solver and a Held–Karp 1-tree replacement bound on synthetic instances and TSPLIB benchmarks. After the fix, the MST-bound solver is exact but proves optimality only up to roughly 20 cities. Look-ahead and regret ordering change node counts by less than 0.4% on every instance where the search completes, whereas the 1-tree bound reduces the root gap from 20–36% to below 1% on random instances, and proves random instances with 25 and 30 cities in 301 and 536 nodes. All eight small TSPLIB instances (n ≤ 42) are solved to proven optimality in under 4 seconds; root bounds for eight instances with 1,060–2,319 cities lie 0.5–2.2% below the reference optima. Clustered instances remain hard for the 1-tree bound. We conclude that the bound, not the branching heuristics, determines the exactness frontier.
Keywords: traveling salesman problem; branch-and-bound; Held–Karp bound; 1-tree; Lagrangian relaxation; branch ordering; TSPLIB.
1. Introduction
The symmetric TSP asks for a minimum-cost Hamiltonian cycle in a complete graph with edge costs c(i,j) = c(j,i). It is NP-hard, and exact methods either enumerate with pruning (branch-and-bound, first proposed for the TSP by Little et al., 1963) or solve linear-programming relaxations with cutting planes (Dantzig, Fulkerson and Johnson, 1954; Applegate et al., 2006). The quality of the relaxation used for pruning is well known to dominate performance; the Held–Karp 1-tree bound (Held and Karp, 1970, 1971) is the classical Lagrangian relaxation used for this purpose.
LDA-B&B is a compact research prototype that emphasises search guidance: a strong initial upper bound from multi-start nearest-neighbour construction with 2-opt, a look-ahead score and a regret tie-break for ordering candidate successors, and a simple residual MST bound for pruning. Its design separates guidance from exactness: ordering rules may change which solution is found first, but only the lower bound and exhaustive completion of non-pruned branches establish optimality. This paper tests that separation empirically and asks three questions.
- RQ1 Is the algorithm correct as specified and as implemented?
- RQ2 How much do look-ahead and regret ordering contribute to the search effort needed to prove optimality?
- RQ3 How far does the exactness frontier move when the MST bound is replaced by a Held–Karp 1-tree bound?
Contributions. We give a formal specification with correctness proofs (Section 3); a complexity analysis of the implementation (Section 4); a documented defect and its consequences (Section 6.1); and an experimental study on synthetic instances and TSPLIB (Sections 5–6).
2. Background
Notation. Let V = {0,…,n−1} with start vertex s = 0. A search node is a partial path s = v₀,…,vₖ = u with cost g and unvisited set U = V \ {v₀,…,vₖ}. UB denotes the incumbent cost. Any completion is a Hamiltonian path from u through all of U ending at s.
Related bounds. The residual MST bound charges the cheapest edge leaving u, an MST on U, and the cheapest edge entering s. The 1-tree bound of Held and Karp adds node penalties π to edge costs, computes a minimum 1-tree, and subtracts 2∑π; every π gives a valid lower bound and subgradient ascent searches for a good π. Cutting-plane codes such as Concorde (Applegate et al., 2006) go beyond this with subtour, comb and other inequalities. TSPLIB (Reinelt, 1991) is the standard benchmark library.
3. The LDA-B&B Algorithm
3.1 Phases
Phase 1: incumbent. For every start vertex, build a nearest-neighbour tour (tie-broken by residual degree), improve it with 2-opt (Croes, 1958), and set UB to the best cost found.
Phase 2: bounding. At each node compute LB = g + min{c(u,x) : x ∈ U} + MST(U) + min{c(x,s) : x ∈ U}; prune if LB ≥ UB.
Phase 3: look-ahead. Order candidates v ∈ U by score(v) = c(u,v) + min{c(v,w) : w ∈ U \ {v}}.
Phase 4: regret. Ties in the look-ahead score are broken by larger regret(v) = second-best continuation − best continuation, then by c(u,v). Regret is used only for ordering.
Phase 5: recursion. Extend the path by each ordered candidate, recurse, and restore state. At a leaf, the closed tour cost g + c(u,s) updates UB if smaller.
3.2 Pseudocode
LDA_BB(c):
UB, T* <- BEST over all starts of TwoOpt(NearestNeighbour(start))
SEARCH(u = 0, U = V\{0}, path = [0], g = 0)
return T*, UB
SEARCH(u, U, path, g):
if U is empty:
if g + c(u,0) < UB: UB <- g + c(u,0); T* <- path
return
if LB(u, U, g) >= UB: return // only safe pruning rule
for v in Order(u, U): // look-ahead, then regret
if g + c(u,v) >= UB: continue // cheap cut-off (c >= 0)
SEARCH(v, U\{v}, path+[v], g + c(u,v))
3.3 Bounds
MST bound. As above. 1-tree (Held–Karp) bound. Let S = {s, u} ∪ U with the edge (u,s) cost set to 0 and forced conceptually. For penalties π ∈ ℝⁿ let cπ(i,j) = c(i,j) + πᵢ + πⱼ, let Tπ be a minimum 1-tree of S under cπ with special node s, and define w(π) = cost(Tπ) − 2∑ᵢπᵢ. The node bound is g + w(π). Penalties are improved by K subgradient steps π ← π + λ (UB−g−w)/||d||² · d, where dᵢ is the degree of node i in Tπ minus 2; λ is halved after four non-improving steps; the ascent stops early when w ≥ UB − g. The root uses 200 steps and interior nodes 12 steps warm-started from root penalties. For integral cost matrices the bound is rounded up.
3.4 Correctness
Lemma 1 (MST bound is valid). Any completion of a node has cost at least LB. Proof. A completion consists of one edge from u into U, a Hamiltonian path on U, and one edge from U to s. The first is at least min c(u,·), the last at least min c(·,s), and a Hamiltonian path on U is a spanning tree of U, hence costs at least MST(U). Summing gives LB. □
Lemma 2 (1-tree bound is valid for every π). Set c'(u,s) = 0. A completion together with edge (u,s) is a Hamiltonian cycle H of S with cost(H) = cost(completion). Every Hamiltonian cycle is a 1-tree in which each node has degree 2, so its cost under cπ is cost(H) + 2∑π. Hence min-1-tree(cπ) ≤ cost(H) + 2∑π, i.e. w(π) ≤ cost(H). Rounding up is valid when all tour costs are integers. □
Theorem (exactness). If the search terminates without a time or node limit, UB equals the optimal tour cost. Proof. UB is the cost of a feasible tour (Phase 1 or a leaf). A branch is discarded only if LB ≥ UB (Lemmas 1–2) or if g + c(u,v) ≥ UB, which is valid because costs are non-negative and the partial cost cannot decrease. Therefore every discarded branch contains no tour of cost < UB, and every other branch is expanded to its leaves. Look-ahead and regret only permute the expansion order and cannot affect this argument. Fixing s = 0 loses no generality because every tour passes through vertex 0. □
Remark. A run that stops at a limit returns the best incumbent found, not a proof.
4. Complexity Analysis
Let n be the number of cities and m = |U| at a node.
4.1 Search-tree size
The number of nodes at depth k is at most (n−1)!/(n−1−k)!, so the tree has at most e·(n−1)! nodes. The implementation fixes only the start vertex; it does not remove the symmetric duplicate obtained by reversing a tour, so the tree is not halved. Worst-case running time is therefore O((n−1)! · poly(n)); as for any exact method for an NP-hard problem, no polynomial worst-case guarantee is expected. Pruning power, not branching order, determines the observed size (Section 6).
4.2 Cost per node
| Component | Cost per node | Note |
|---|---|---|
| MST bound (dense Prim) | O(m²) | Python loops over dict keys |
| Ordering (look-ahead + regret) | O(m² log m) | sort m continuations per candidate |
| Child construction | O(m log m + n) | sorted tuple of U; path copy |
| 1-tree bound, K ascent steps | O(K·m²) | vectorised Prim per step, K = 12 (200 at root) |
Table 1. Per-node operation counts of the implementation. Node cost is Θ(m² log m) with the MST bound and Θ(K m² + m² log m) with the 1-tree bound.
Total time is (nodes expanded) × (cost per node), so a stronger bound is profitable exactly when it removes more nodes than the factor K it adds to node cost.
4.3 Construction phase
The algorithm description states that nearest-neighbour construction costs O(n²) per start vertex. The implementation costs O(n³) per start: for each of the n steps it evaluates n candidates, and each evaluation of the residual-degree tie-break builds a set difference and scans it in O(n). Moreover, in a complete graph the residual degree of every unvisited candidate equals |U|−1, so the tie-break is identical for all candidates and carries no information; “degree-aware” selection is vacuous on the complete graphs the algorithm is specified for. Removing it restores O(n²) per start.
The 2-opt routine scans O(n²) vertex pairs per pass and restarts the scan after each improving move (each reversal costing O(n)), giving O(I·n²) for I improving moves. The multi-start phase repeats this for all n starts, which is impractical beyond a few hundred vertices in pure Python.
4.4 Space
The distance matrix uses O(n²) memory (about 2.7 GB in float64 for n = 18,512). The recursion has depth n and each frame holds a path copy and a sorted tuple of size O(n), so the stack costs O(n²) in the worst case. Dense storage is the practical scaling limit for the mid-size and large TSPLIB instances.
4.5 Reference exact method
Held–Karp dynamic programming solves the TSP in O(n² 2ⁿ) time and O(n 2ⁿ) space. We use it (n ≤ 16) to validate LDA-B&B.
5. Experimental Setup
Implementations. (a) the uploaded prototype as supplied; (b) the prototype with the defect of Section 6.1 fixed (MST bound); (c) the fixed prototype with the 1-tree bound of Section 3.3. All are Python 3 with NumPy for (c); look-ahead and regret are enabled unless stated.
Instances. Synthetic: random Euclidean (integer-rounded, coordinates in [0,1000]), 4-cluster Euclidean, grid, and random non-metric symmetric matrices, single seeds. TSPLIB: burma14, ulysses16, gr17, gr21, gr24, fri26, bayg29, dantzig42 (exact search) and u1060, vm1084, d1291, u1432, d1655, vm1748, u2152, u2319 (root bound only). Distance functions follow the TSPLIB specification (EUC_2D, GEO, explicit matrices). Reference optima are the published values as recalled by the author, not recomputed here.
Protocol. Time limits of 30–150 s per synthetic run and 150 s for TSPLIB search runs; a run is called proven only if it terminated without a limit. Correctness was checked against Held–Karp DP on 60 mixed instances with 5 ≤ n ≤ 11 for both fixed solvers (120 runs). Limitations: one machine, single seeds, no repetition-based confidence intervals, and interpreted Python; absolute times are not comparable with compiled codes.
Mid-size bounds. For n ≥ 1,060 we ran 100 subgradient steps at the root only, using the reference optimum as the step-size target. Because the bound is valid for every π this choice affects tightness, not validity, but the resulting gaps should be read as “achievable with a good target”.
6. Results
6.1 A defect in the supplied MST routine
The routine mst_cost starts Prim's algorithm with used = {vertices[0]} and key[vertices[0]] = 0 but never relaxes the edges of the first vertex. All other keys remain infinite, the first “selected” key is infinity, and the function returns ∞. The lower bound is therefore infinite at the root, the root is pruned, and the solver returns the multi-start 2-opt tour after one node while reporting a completed proof. On a random 16-city instance it returned 3,759 with “proof completed”, whereas the true optimum (Held–Karp DP) is 3,753. Initialising used as the empty set fixes it. On all twelve instances of our initial test ladder (10–25 cities, random, clustered, grid and non-metric) the uncorrected solver reported nodes = 1 and proven = true, including rand16 where the incumbent was suboptimal. The defect is a false-proof failure: the heuristic answer is presented as certified. A regression test against Held–Karp DP catches it and we recommend it as a minimum release criterion.
6.2 Synthetic instances: MST versus 1-tree bound
| Instance | n | MST bound | 1-tree bound | Root gap (MST) |
|---|---|---|---|---|
| random | 10 / 12 / 14 | 427 / 2,978 / 6,344 nodes | not run | — |
| clustered | 14 | 84,509 nodes, 1.4 s | not run | — |
| random | 16 | 20,979 nodes, 0.5 s | not run | — |
| random | 20 | 163,106 nodes, 4.8 s | 1 node | 21.0% |
| grid 5×5 | 25 | 25,903 nodes, 0.8 s | not run | — |
| non-metric | 22 | 961,175 nodes, 30 s | 223 nodes, 0.1 s | 27.1% (n=20) |
| random | 25 | not proven (60 s), 1.46M nodes | 301 nodes, 0.1 s | 19.5% |
| clustered | 22 | not proven (60 s), 2.1M nodes | not proven (120 s), 324k nodes | 36.1% |
| random | 30 | not proven (90 s), 1.73M nodes | 536 nodes, 0.1 s | — |
| clustered | 30 | not proven (90 s), 2.18M nodes | not proven (120 s), 300k nodes | — |
Table 2. Synthetic results after the defect fix. Root gap = (UB − root LB)/UB with the MST bound. The 1-tree solver found the optimum 4,579 on random-30, equal to the best tour from an independent 2-opt + Or-opt random-restart search, which the unproven MST run (4,614) had missed.
With the 1-tree bound the root gap on random instances falls below 1%, so the incumbent from Phase 1 is proven optimal at, or within a few hundred nodes of, the root. Clustered instances keep a 13–16% root gap under the 1-tree bound plausibly because a 1-tree can connect clusters through cheap intra-cluster edges without the global constraint that a tour crosses between clusters exactly once.
6.3 Ablation of ordering heuristics
| Instance | Look-ahead + regret | Look-ahead only | No ordering heuristics |
|---|---|---|---|
| clustered n=14 | 84,509 | 84,509 | 84,509 |
| random n=16 | 20,979 | 20,979 | 20,908 |
| random n=20 | 163,106 | 163,106 | 163,106 |
| grid 5×5 | 25,903 | 25,903 | 25,903 |
Table 3. Nodes expanded to prove optimality (MST bound). Regret is identical to look-ahead only on every instance; the no-heuristic variant differs by −0.3% on one instance.
When the incumbent from Phase 1 is already optimal, all branches with LB < UB must be explored regardless of order, so ordering can change nothing but the moment at which a better tour is discovered, and here none is. This matches the algorithm's own statement that ordering does not establish optimality, and shows that it also barely accelerates the proof.
6.4 TSPLIB: exact search on small instances
| Instance | n | Cost | Reference opt. | Nodes | Time (s) | MST bound, 40 s |
|---|---|---|---|---|---|---|
| burma14 | 14 | 3323 | 3323 | 1 | 0.0 | — |
| ulysses16 | 16 | 6859 | 6859 | 1 | 0.0 | — |
| gr17 | 17 | 2085 | 2085 | 1 | 0.0 | not proven |
| gr21 | 21 | 2707 | 2707 | 1 | 0.0 | proven, 137k nodes |
| gr24 | 24 | 1272 | 1272 | 1 | 0.1 | not proven |
| fri26 | 26 | 937 | 937 | 1 | 0.0 | not proven |
| bayg29 | 29 | 1610 | 1610 | 651 | 0.3 | not proven |
| dantzig42 | 42 | 699 | 699 | 6,915 | 3.7 | not proven |
Table 4. LDA-B&B with the 1-tree bound on TSPLIB, all proven optimal and equal to the reference values. The last column reports the MST-bound solver; it found the optimal tour in each case but could not certify it except on gr21.
For six of the eight instances the root 1-tree bound equals the Phase 1 incumbent, so the proof is a single bound evaluation. The remaining effort is concentrated on bayg29 and dantzig42.
6.5 TSPLIB: root bounds on mid-size instances
| Instance | n | Root 1-tree bound | Reference optimum | Gap |
|---|---|---|---|---|
| u1060 | 1060 | 220,275 | 224,094 | 1.70% |
| vm1084 | 1084 | 235,367 | 239,297 | 1.64% |
| d1291 | 1291 | 49,683 | 50,801 | 2.20% |
| u1432 | 1432 | 151,941 | 152,970 | 0.67% |
| d1655 | 1655 | 61,124 | 62,128 | 1.62% |
| vm1748 | 1748 | 331,420 | 336,556 | 1.53% |
| u2152 | 2152 | 63,680 | 64,253 | 0.89% |
| u2319 | 2319 | 233,096 | 234,256 | 0.50% |
Table 5. Root Held–Karp bounds (100 subgradient steps, 2–10 s each). No branch-and-bound search was run on these instances. The four largest supplied instances (brd14051, d15112, usa13509, d18512) were not run because a dense distance matrix is prohibitive.
7. Discussion
Key findings. (1) The bound determines the exactness frontier: replacing the MST bound with a 1-tree bound moved the largest proven random instance from about 20 to at least 30 cities and cut node counts by three to five orders of magnitude. (2) Look-ahead and regret are cosmetic for proving optimality; they may still matter for anytime behaviour when the incumbent is weak, which our instances did not exercise. (3) The multi-start 2-opt incumbent is strong on small instances (optimal on all eight TSPLIB cases) but time-limited search cannot be trusted on larger ones: the unproven random-30 run ended 0.8% above the optimum. (4) Structure matters: clustered instances resist the 1-tree bound, pointing to subtour-elimination cuts as the next step. (5) An unverified bound routine can silently convert a heuristic into a false certificate.
Threats to validity. Single seeds; one hardware setting; interpreted code; reference optima taken from memory of the published tables; subgradient step-size target on mid-size runs set to the reference optimum; the mid-size instances were not searched; the definition of “most complex” instance was limited to the largest sizes we could execute exactly.
7.1 Recommendations
- Adopt the 1-tree bound as the default and keep the MST bound only as a fast fallback.
- Add the Held–Karp DP regression test to the release pipeline.
- Drop the vacuous degree tie-break, or replace it with a non-trivial signal such as the 1-tree node degree.
- For clustered instances add subtour-elimination or comb cuts; for n ≥ 1,000 use sparse candidate graphs and compiled code.
8. Conclusion
LDA-B&B is correct by design but the supplied implementation was not correct in practice: a single initialisation error made every proof vacuous. After correction, the algorithm is exact, and its strength comes from the lower bound rather than from ordering heuristics. A Held–Karp 1-tree bound proves all small TSPLIB instances tested in seconds and random instances up to 30 cities, while clustered instances mark the boundary where stronger relaxations are needed.
References
Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812.
Dantzig, G., Fulkerson, R., and Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393–410.
Held, M., and Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the SIAM, 10(1), 196–210.
Held, M., and Karp, R. M. (1970). The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6), 1138–1162.
Held, M., and Karp, R. M. (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1, 6–25.
Little, J. D. C., Murty, K. G., Sweeney, D. W., and Karel, C. (1963). An algorithm for the traveling salesman problem. Operations Research, 11(6), 972–989.
Reinelt, G. (1991). TSPLIB — a traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384.