Travelling Salesman Problem Branch And Bound

Travelling Salesman Problem and the Branch‑and‑Bound Technique

The travelling salesman problem (TSP) is one of the most studied combinatorial optimisation challenges in computer science and operations research. On top of that, given a set of cities and the distances between every pair, the goal is to find the shortest possible tour that visits each city exactly once and returns to the starting point. Although the problem statement is simple, solving TSP exactly is NP‑hard, meaning that the time required grows exponentially with the number of cities. For modest‑size instances, the branch‑and‑bound method provides a powerful exact algorithm that systematically explores the solution space while discarding large portions that cannot lead to an optimal tour.

Why Branch‑and‑Bound Works for TSP

Branch‑and‑bound combines two ideas:

1. Branching – recursively partitioning the set of feasible tours into smaller sub‑problems (branches).
2. Bounding – computing a lower bound on the cost of any tour that can be completed from a given partial solution; if this bound exceeds the best tour found so far, the entire branch can be pruned.

By keeping track of the best complete tour (the incumbent) and using tight bounds, the algorithm often explores only a tiny fraction of the factorial number of permutations, making exact solutions feasible for instances with up to a few dozen cities on modern hardware.

This is the bit that actually matters in practice.

Core Steps of the Branch‑and‑Bound Algorithm for TSP

Below is a typical outline that can be adapted to symmetric or asymmetric TSP formulations And it works..

1. Initialisation

   • Compute an initial upper bound (incumbent) using a fast heuristic such as the nearest‑neighbour or Christofides algorithm.
   • Set the best known tour length UB to this heuristic value.

2. Root Node Creation

   • The root represents the empty partial tour (no edges fixed).
   • Compute a lower bound LB(root) for the root using a relaxation (e.g., assignment problem or minimum spanning tree).

3. Branching Rule

   • Select a city i that is not yet connected in the partial tour.
   • Generate two child nodes: one where edge (i, j) is included and another where it is excluded (for all feasible j).
   • Each child inherits the fixed edges of its parent plus the new decision.

4. Bounding Function

   • For each child, recompute a lower bound that respects the fixed edges:
     • Inclusion bound – add the cost of forced edges and solve a relaxed assignment problem on the remaining vertices.
     • Exclusion bound – prohibit the excluded edge and solve the same relaxation.
   • If LB(child) ≥ UB, discard (prune) the child; otherwise keep it for further exploration.

5. Node Selection Strategy

   • Use a priority queue (best‑first search) ordered by increasing lower bound, or a depth‑first stack with backtracking.
   • Best‑first tends to find good incumbents early, improving pruning.

6. Updating the Incumbent

   • When a node represents a complete tour (all cities have degree 2 and the graph forms a single cycle), compute its exact length.
   • If this length < UB, set UB to the new value and store the tour as the best solution found.

7. Termination

   • The algorithm stops when the priority queue is empty (all nodes processed or pruned).
   • At that point, UB equals the optimal tour length, and the stored tour is optimal.

Illustrative Example (4‑City Symmetric TSP)

Consider cities A, B, C, D with the distance matrix:

1. Heuristic upper bound – nearest‑neighbour from A yields A→B→D→C→A with length 10+25+30+15 = 80. Set UB = 80.
2. Root lower bound – solving the assignment problem gives a bound of 65 (the sum of the two smallest outgoing edges per vertex). Since 65 < 80, we continue.
3. Branch on edge (A,B)
   • Include (A,B) – forced edge reduces the problem; new lower bound = 70.
   • Exclude (A,B) – prohibit A‑B; new lower bound = 68.
   • Both bounds < 80, so both children stay alive.
4. Proceed depth‑first – suppose we explore the include branch first.
   • Next decision: include (B,C) vs exclude (B,C).
   • Include (B,C) forces a partial path A‑B‑C; lower bound becomes 78.
   • Exclude (B,C) gives bound 72.
5. When a complete tour emerges – the path A‑B‑D‑C‑A (all forced/included decisions) evaluates to 80, matching the incumbent.
6. Pruning – any node whose lower bound reaches or exceeds 80 is discarded. After exploring all branches, the algorithm confirms that no tour shorter than 80 exists, thus the incumbent is optimal.

Even though this tiny instance could be solved by inspection, the same logic scales: each bound eliminates large swaths of the permutation tree, drastically reducing the search effort And that's really what it comes down to..

Advantages of Branch‑and‑Bound for TSP

• Exactness – guarantees optimality when the algorithm finishes.
• Flexibility – works for symmetric, asymmetric, and even weighted variants (e.g., time windows) by adjusting the bounding relaxation.
• Strong pruning – good lower bounds (assignment, 1‑tree, Held‑Karp) cut off exponential portions of the search tree.
• Incremental improvement – the incumbent improves as soon as a feasible tour is found, tightening future bounds.

Limitations and Practical Considerations

• Bounding quality matters – a weak bound leads to little pruning, causing the algorithm to degenerate to brute force.
• Memory usage – storing many live nodes in a priority queue can become large; depth‑first variants reduce memory but may miss early good incumbents.
• Scalability – for instances beyond ~50‑60 cities, even the best branch‑and‑bound implementations struggle without additional techniques (cutting planes, heuristic tours, parallelism).
• Implementation complexity – designing efficient data structures for the relaxation (e.g., solving

the assignment problem or 1‑tree subproblems) and for branching decisions (e.So g. , choosing the most fractional variable or the edge that maximally increases the bound) requires significant engineering effort Small thing, real impact..

Modern Enhancements: Branch‑and‑Cut

In practice, pure branch‑and‑bound has largely been superseded by branch‑and‑cut for large‑scale TSP. Consider this: by solving a sequence of LPs strengthened with these cuts, the lower bound at each node becomes dramatically stronger, often closing the gap to optimality without deep branching. This paradigm integrates the bounding and branching framework with cutting planes—valid inequalities (such as subtour‑elimination constraints, comb inequalities, and clique cuts) that tighten the linear programming relaxation dynamically. The state‑of‑the‑art solver Concorde exemplifies this approach, routinely solving instances with tens of thousands of cities to proven optimality.

Heuristic Integration

A practical implementation almost always couples the exact engine with powerful heuristics:

• Construction heuristics (nearest neighbor, Christofides) and improvement heuristics (2‑opt, 3‑opt, Lin‑Kernighan) quickly produce high‑quality incumbents, lowering the global upper bound early.
• Local search is frequently embedded inside the tree (e.g., at every node) to attempt to complete a partial solution into a full tour, potentially improving the incumbent and triggering further pruning.
• Warm‑starting the LP relaxation with the basis from the parent node drastically reduces re‑optimization time.

Parallelism and Hardware

Modern branch‑and‑cut implementations exploit parallelism at multiple levels: a parallel tree search distributes live nodes across cores or compute nodes, while parallel LP solvers accelerate the bound computation at individual nodes. Careful load balancing and deterministic tie‑breaking are essential to ensure reproducibility and avoid redundant work.

Conclusion

Branch‑and‑bound remains the conceptual backbone of exact TSP solution methods. That's why while the vanilla algorithm illustrated on the four‑city example is pedagogically clear, its industrial‑strength descendants—branch‑and‑cut solvers armed with polyhedral theory, sophisticated heuristics, and massive parallelism—have pushed the frontier of provable optimality from dozens to tens of thousands of cities. Understanding the interplay between bounding (how tightly we can estimate the best possible completion), branching (how we partition the search space), and pruning (how we discard hopeless regions) is essential not only for TSP but for the vast majority of combinatorial optimization problems where exact solutions are required. As hardware advances and cutting‑plane libraries mature, the line between "intractable" and "solvable" continues to recede, cementing branch‑and‑bound’s legacy as a foundational algorithmic paradigm Small thing, real impact..