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.
Take any formulation of TSP with binary variables $x_{i,j}$ that indicate whether edge $(i,j)$ is traversed. Now introduce a $k$ index for person $k$ (this is a different meaning than your $k$), include that in every variable ($x_{i,j,k}$), and make $k$ copies of each constraint. So far, the problem is separable by $k$. To enforce edge-disjointness, impose one additional family of "linking" constraints across $k$:
$$\sum_k x_{i,j,k} \le 1 \quad \text{for each $(i,j)$}$$
Best Answer
Example: Lp Formulation of TSP
Consider the following distance-matrix of 4-Cities TSP:
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
The Route is: X12 – X23 – X34 – X41 = 59