Upper & Lower Bounds for the Travelling Salesman Problem
Feasibility versus guarantee: An upper bound always comes from an actual Hamiltonian cycle, so it is constructive and directly checkable. A lower bound does not need to be a tour; it only needs mathematically valid reasoning that every tour must be at least that large. This difference explains why upper-bound methods focus on route construction while lower-bound methods focus on structural constraints.
Tightness matters: The usefulness of bounds depends on the gap , not just on either value alone. A small gap means high confidence in the true optimum and often allows fast termination of further work. If the two bounds are equal, optimality is certified immediately.
Upper bound via MST doubling: First compute an MST using Prim or Kruskal, then set initial upper bound . This guarantees a closed walk that covers all vertices, so it is always feasible as a starting ceiling. It is best used when you need a fast, provably valid UB before refinement.
Upper bound improvement by shortcuts: Identify repeated pathways in the doubled-tree traversal and replace them with direct edges when those direct edges are cheaper. The update is conceptualized as removing a repeated chain and inserting a single edge, reducing total weight while preserving a complete tour. This step is effective in metric graphs where triangle inequality supports shortcut validity.
Lower bound via deleted-vertex method: For a chosen deleted vertex , compute on the remaining vertices. Add the two smallest edges incident to , say and , to obtain one candidate lower bound. The formula is:
| Feature | Upper Bound (MST/Nearest-Neighbour Tour) | Lower Bound (Deleted-Vertex + RMST) |
|---|---|---|
| Output type | Feasible Hamiltonian cycle or cycle length | Guaranteed minimum threshold |
| Mathematical direction | Shows solution is at most this value | Shows solution is at least this value |
| Typical objective | Minimize UB | Maximize LB |
| Equality implication | UB = LB proves optimality | LB alone does not ensure feasibility |
| Core structure used | Full tour construction | RMST plus two reconnecting edges |
Start with bound direction checks: Before computing, state whether the task asks for a value to minimize (UB) or maximize (LB). This single decision determines whether you should build tours or build RMST-based inequalities. It also prevents sign errors when interpreting improvements.
Use a verification checklist: For upper bounds, confirm the final route is a Hamiltonian cycle and includes return to start exactly once in the final count. For lower bounds, confirm you added exactly two reconnecting edges to the deleted vertex and did not accidentally reuse path lengths instead of individual edge weights. These checks catch most mark-losing errors.
Reasonableness test at the end: Ensure your final numbers satisfy and explain what equality would imply. If UB falls below a previously proven LB, retrace arithmetic because the result is logically impossible. A short logical audit often saves more marks than extra computation.
Misconception: any low value is a lower bound: A lower bound must come from a valid argument that applies to all tours, not from a guessed short route. Students sometimes report a small route as LB even though it is actually an upper bound candidate. Always ask whether the number is proving a floor or exhibiting a ceiling.
Error in deleted-vertex method: A frequent mistake is adding only one connecting edge from the deleted vertex to the RMST. Every Hamiltonian cycle uses two incident edges at each vertex, so one edge cannot represent a cycle-compatible reconnection. This systematically underestimates the lower bound and weakens conclusions.
Shortcut misuse in upper bounds: Replacing repeated chains with direct edges is valid only when the replacement still preserves a complete visit-and-return tour. If a shortcut disconnects the visit order or skips required vertices, the resulting value is not a feasible UB. Always validate feasibility after each reduction.
Relation to approximation algorithms: The MST-doubling idea is a foundation for approximation guarantees in metric TSP, where triangle inequality allows shortcutting without increasing cost. This links school-level techniques to formal algorithm design in computer science. Understanding the bound logic here builds intuition for approximation ratios later.
Role in branch-and-bound workflows: Practical exact solvers repeatedly compute lower and upper bounds to prune search trees, keeping only promising partial solutions. A stronger LB removes more branches, while a better UB tightens acceptance thresholds. The classroom methods mirror this professional optimization strategy in simplified form.