For the TSP of Example 15.1.2, we obtain the minimal spanning tree T with w ( T ) = 186 shown in Figure 15.2. This bound is slightly inferior to the one provided in Example 15.2.1, but determining a...

For the TSP of Example 15.1.2, we obtain the minimal spanning tree
T
with
w(T) = 186 shown in Figure 15.2. This bound is slightly inferior to the one provided in Example 15.2.1, but determining a minimal spanning tree is also much easier than solving an AP. Note that the MST relaxation leaves out the weight of one of the edges of the tour, and hence is unnecessarily weak. This observation motivates a variation which we consider next.