Heuristics usually provide sub-optimal solutions, so we need some kind of guideline to measure how close to optimal our sub-optimum is. Such a measure, in the case of the Travelling Salesman Problem (TSP), can be obtained by finding a lower bound for the length of the shortest possible tour.
Lower bounds are generally obtained by solving relaxations of the TSP at hand, i.e. we relax the constraints of the TSP until we have a problem that we can solve efficiently. We can then find the optimum solution of the relaxed problem, which is a valid lower bound for the original TSP.
Our goal here is to find relaxations of the TSP that are easier to solve, and provide lower bounds that are as ‘tight’ as possible. Note that if our relaxed problem also happens to produce a valid tour, then that tour is the true optimum solution to the original TSP.
One approach to relaxing the TSP to provide lower bounds involves minimum spanning trees.
The 1-tree bound for the TSP relaxes the problem by selecting one vertex, v, and dividing any TSP solution into a path, P, amongst the remaining N - 1 vertices in V \ v, and the two edges, e1 and e2, connecting v to the ends of the path.
Now we can provide a lower bound by simply choosing an arbitrary v, any path in V \ v, and simply connecting v to the ends of the path. The resulting edge-cost (c(e1) + c(e2) + C(P), where C(X) is the cost of some connected set of vertices, X) would be a lower bound for the TSP solution. Although efficient, this method is obviously lacking as the lower bound provided could be substantially less than the optimum. We need to increase the tightness of the bound, while making sure it doesn’t exceed the edge-cost of the optimal tour.
Defining the optimal TSP tour as T edges in E, we have
T = c(e1) + c(e2) + C(P).
If we then set A and B as
(i) A <= c(e1) + c(e2) and
(ii) B <= C(P),
then A + B is a lower bound for C(T).
For A to always maintain condition (i), we can define it as the total cost of the two cheapest edges in G.
For B, however, the situation is more tricky – we cannot define it as the minimum ‘spanning path’ on G \ v (it would be just as hard as the TSP). Instead, we define it as the minimum spanning tree on G \ v (the 1-tree), which is computed in polynomial-time by Prim’s algorithm. Since the minimum spanning tree will always have a smaller edge-cost than any spanning path, P, we maintain condition (ii).
Therefore, A + B forms a lower bound for the TSP.
The 1-tree bound is reasonably tight, but it may be unsatisfactory in some cases. Using different vertices, v, we can increase the lower bound, but by no significant amount. If we are to produce an even tighter bound, we must turn to other bounding techniques, such as the Held-Karp bound.