10.6.2 Upper & Lower Bounds for the Travelling Salesman Problem

When solving the Travelling Salesman Problem (TSP), it is often useful to estimate the solution using upper and lower bounds. These bounds can help determine how close a given solution is to the optimal solution. The bounds are often derived using minimum spanning tree (MST) methods and techniques for handling incomplete networks.

Upper and Lower Bounds for TSP

Lower Bound: Minimum Spanning Tree Method

The lower bound represents the smallest possible distance for a valid TSP route, though it may not always be achievable.

Steps to Calculate the Lower Bound:

Convert to a Complete Network
Construct a Minimum Spanning Tree (MST)
Add Two Smallest Edge Weights
Calculate the Lower Bound

Convert to a Complete Network:

If the graph is incomplete, calculate the shortest paths between all pairs of vertices to form a complete network. Replace missing edges with these shortest distances.

Construct a Minimum Spanning Tree (MST):

Use an algorithm such as Prim's or Kruskal's to construct the MST for the graph.
The MST represents the shortest total distance required to connect all vertices without forming a cycle.

Add Two Smallest Edge Weights:

Identify the two smallest edges connected to the starting vertex.
Add these weights to the total weight of the MST.

Calculate the Lower Bound:

\text{Lower Bound} = \text{Weight of MST} + \text{Two Smallest Edge Weights}

Upper Bound: Nearest Neighbour Algorithm

The upper bound represents an achievable (though not necessarily optimal) route length.

Steps to Calculate the Upper Bound:

Use the Nearest Neighbour Algorithm
Calculate the Total Distance
Improve the Upper Bound

Use the Nearest Neighbour Algorithm:

Start at a given vertex.
Move to the nearest unvisited vertex at each step.
Repeat until all vertices are visited, then return to the starting vertex.

Calculate the Total Distance:

Sum the weights of the edges in the route to find the upper bound.

Improve the Upper Bound:

Examine the route and use shortcuts to replace sections of the path with shorter alternatives, ensuring the route remains a Hamiltonian cycle.

Worked Example

infoNote

Question: Find the upper and lower bounds for the TSP in the graph below:

	A	B	C	D
A	∞	10	15	20
B	10	∞	35	25
C	15	35	∞	30
D	20	25	30	∞

Step 1: Lower Bound Using MST

Construct the MST:

Use Prim's Algorithm to find the MST for the graph:

Start at $A$ , connect $A \to B$ (10)
From $B$ , connect $B \to D$ (25)
From D, connect $D \to C$ (30) MST Weight:

10 + 25 + 30 = :highlight[65]

Add Two Smallest Edges from $A$ :

The smallest edges connected to $A$ are $A \to B = :highlight[10]$ and $A \to C = :highlight[15]$

Lower Bound:

65 + 10 + 15 = :highlight[90]

Step 2: Upper Bound Using Nearest Neighbour

Nearest Neighbour Algorithm:

Start at $A$ . Nearest vertex: $B$ (10)
From $B$ , move to $D$ (25)
From $D$ , move to $C$ (30)
Return to $A$ (15) Route: $A \to B \to D \to C \to A$

Upper Bound:

$10 + 25 + 30 + 15 = :highlight[80]$

Improvement:

Review the route for possible shortcuts. In this case, the upper bound remains at 80, as no shorter Hamiltonian cycle can be formed.

Note Summary

infoNote

Common Mistakes

Incorrect MST Calculation: Errors in constructing the MST, such as including cycles or missing edges, can lead to incorrect lower bounds.
Forgetting to Add Two Smallest Edges: Omitting the additional weights needed for the lower bound calculation results in an underestimate.
Ignoring Shortcuts for Upper Bounds: Failing to refine the initial upper bound can leave suboptimal solutions.
Misinterpretation of Incomplete Graphs: Not converting the graph into a complete network by finding shortest paths between disconnected vertices.
Confusion Between Bounds: Mixing up the roles of upper and lower bounds when interpreting results.

infoNote

Key Formulas/Theorems

Lower Bound Formula:

\text{Lower Bound} = \text{Weight of MST} + \text{Two Smallest Edge Weights from the Starting Vertex}

Upper Bound Calculation:

\text{Upper Bound} = \text{Total Weight of Hamiltonian Cycle (via Nearest Neighbour or Shortcuts)}

Minimum Spanning Tree (MST): The MST is the tree connecting all vertices with the smallest total edge weight and no cycles.
Triangle Inequality:

\text{Weight of } (A \to C) \leq \text{Weight of } (A \to B) + \text{Weight of } (B \to C)

Upper & Lower Bounds for the Travelling Salesman Problem Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1

10.6.2 Upper & Lower Bounds for the Travelling Salesman Problem

Upper and Lower Bounds for TSP

Lower Bound: Minimum Spanning Tree Method

Steps to Calculate the Lower Bound:

Upper Bound: Nearest Neighbour Algorithm

Steps to Calculate the Upper Bound:

Worked Example

Note Summary

Common Mistakes

Key Formulas/Theorems

500K+ Students Use These Powerful Tools to Master Upper & Lower Bounds for the Travelling Salesman Problem For their A-Level Exams.

Other Revision Notes related to Upper & Lower Bounds for the Travelling Salesman Problem you should explore