The proof/stems from the following $3$ observations about a tour $T$
- $T$ for each $v$, $T$ contains exactly two edges adjacent to $v$, and
- The sum of the weights of those two edges is at least the sum of the two lowest weights of edges adjacent to $v$.
- If $e_1(v)$ and $e_2(v)$ denote the edges adjacent to $v$ of smallest and second smallest weights (resp.) then either $e_1(v)$ and $e_2(v)$ are in $T$ or the sum of the weights of the two edges in $T$ adjacent to $v$ exceeds the sum of the weights $w_1(v)$ and $w_2(v)$ of $e_1(v)$ and $e_2(v)$.
Keeping (1) - (3) in mind, what is the total weight $W$ of $T$? If we denote by $w(e)$ the weight of an edge $e$ we might consider
$$
\sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))],
$$
where $t_1(v)$ and $t_2(v)$ are the two distinct edges in $T$ adjacent to $v$. But since every edge in $T$ is adjacent to two vertices $v$, this sum contains the wait of each edge $e$ in $T$ twice, and hence equals $2W$. Since (3) is summarized by the statement $w(t_1(v)) + w(t_2(v)) \geq w_1(v) + w_2(v)$, we conclude
$$
W = \frac{1}{2}\sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))]
\geq \frac{1}{2}\sum_{v \text{ in } T}[w_1(v) + w_2(v)],
$$
which is the desired lower bound.
Example: Lp Formulation of TSP
Consider the following distance-matrix of 4-Cities TSP:
To
From 1 2 3 4
1
13 21 26
2 10
29 20
3 30 20
5
4 12 30 7
Exclude the the Diagonal Variables (X11, X22, X33, X44) from the Distance Table as shown above
The following table represents the Assignment Model + the Additional Constraints resulting from ui – uj + n xij <= n-1; i,j = 2, . ., n & i ≠ j
n = 4
ui – uj + n xij <= 3; i,j = 2, . ., n & i ≠ j
n xij + ui – uj <= 3
4 X23 + U2 – U3 ≤ 3 (i = 2, j = 3)
4 X24 + U2 – U4 ≤ 3 (i = 2, j = 4)
4 X32 + U3 – U2 ≤ 3 (i = 3, j = 2)
4 X34 + U3 – U4 ≤ 3 (i = 3, j = 4)
4 X42 + U4 – U2 ≤ 3 (i = 4, j = 2)
4 X43 + U4 – U3 ≤ (i = 4, j = 3)
V’s X12 X13 X14 X21 X23 X24 X31 X32 X34 X41 X42 X43
U2 U3 U4
OF 13 21 26 10 29 20 30 20 5 12 30 7
1
1 1 1 = 1
2 1 1 1 = 1
3 1 1 1 = 1
4
1 1 1 = 1
5 1 1 1 = 1
6 1 1 = 1
7 1 1 1 = 1
8
1 1 1 = 1
9 4 1 -1 ≤ 3
10 4 1 -1 ≤ 3
11 1 -1 1 ≤ 3
12 1 1 -1 ≤ 3
13 4 -1 1 ≤ 3
14 1 -1 1 ≤ 3
The associated LP consists of the Assignment Model + the Additional Constraints.
Minimize 13X12 + 21X13 + 26X14 + 10X21 + 29X23 + 20X24 + 30X31 +
20X32 + 5X34 + 12X41 + 30X42 + 7X43
s.to:
C1 1X12 + 1X13 + 1X14 = 1
C2 1X21 + 1X23 + 1X24 = 1
C3 1X31 + 1X32 + 1X34 = 1
C4 1X41 + 1X42 + 1X43 = 1
C5 1X21 + 1X31 + 1X41 = 1
C6 1X12 + 1X32 + 1X42 = 1
C7 1X13 + 1X23 + 1X43 = 1
C8 1X14 + 1X24 + 1X34 = 1
C9 4X23 + 1U2 - 1U3 <= 3
C10 4X24 + 1U2 - 1U4 <= 3
C11 4X32 - 1U2 + 1U3 <= 3
C12 4X34 + 1U3 - 1U4 <= 3
C13 4X42 - 1U2 + 1U4 <= 3
C14 4X43 - 1U3 + 1U4 <= 3
Integer: U2, U3, U4 Binary: All Xs
Solution Summary for LP of TSP:
Decision Solution Unit Cost or
Variable Value Profit C(j)
1 X12 1.0000 13.0000
2 X13 0 21.0000
3 X14 0 26.0000
4 X21 0 10.0000
5 X23 1.0000 29.0000
6 X24 0 20.0000
7 X31 0 30.0000
8 X32 0 20.0000
9 X34 1.0000 5.0000
10 X41 1.0000 12.0000
11 X42 0 30.0000
12 X43 0 7.0000
13 U2 0 0
14 U3 1.0000 0
15 U4 2.0000 0
Objective Function (Min.) = 59.0000
The Route is: X12 – X23 – X34 – X41 = 59
Best Answer
Let's look at an example. Suppose you have four cities, A, X, Y, and Z, and A is at distance $1$ from each of the others, while the distance between any two of X, Y, Z is $100$. Then of course a solution to TSP starting at A is given by A to X to A to Y to A to Z to A – let's write this as AXAYAZA, which has length $6$, and visits A multiple times.
Now let's carry out the construction in Rahul's comment. We form a new problem with the same cities but with the distance between cities replaced by the length of the shortest path between the two cities. So in the new problem, A is still at distance $1$ from each of the others, but the distance between any two of X, Y, Z is $2$. Now the tirangle inequality is satisfied (although the configuration is still unrealizable in any Euclidean space), and a solution is given by AXYZA, length $6$, no city visited twice (except for both starting and ending at A).
So we have taken a problem where the solution has multiple visits to a city, and replaced it with an equivalent problem which doesn't. I hope it's clear that you can carry out this construction for any (finite) set of cities and distances. So you can always replace a problem with an equivalent problem where the triangle inequality is satisfied and no city gets visited more than once. So, there is no loss of generality in assuming the triangle inequality holds and no city gets visited more than once. That's why we can restrict our attention to what looks like, but really isn't, a special case.