# Linear Programming Formulation of Traveling Salesman (TSP) in Wikipedia

I am confused by Wikipedia's Linear Programming formulation of the Traveling Salesman Problem, in say the objective function.

Question: If there are n cities indexed 1,...,n, what is city with index 0?

This can be seen in the objective function which has the summation of $c_{ij} x_{ij}$ from i=0...n. Also seen in the third and forth constraint.

It seems like Wikipedia's ILP formulation of the TSP is wrong/incomplete. What changes are needed to make it correct?

There is also an older/different version of the formulation, is this correct?

And another one found on Stackexchange

• interesting read: en.wikipedia.org/wiki/… People seem to be aware that the formulation is wrong and why it's wrong, but have not fixed it yet. – LinAlg Oct 6 '16 at 22:44
• @LinAlg Thanks for pointing that out with the wiki talk page. With my extremely limited knowledge in TSP and ILP, I cannot figure out the correct formulations. Do you mind writing an answer with the correct range for i and j? – Nyxynyx Oct 6 '16 at 23:04
• A long time ago I published a paper about the $\texttt{Traveling Salesman Problem}$: New Monitoring Parameter for the Traveling Salesman Problem. F. P. Marin, Phys. Rev. Letters, $\mathbf{77}$, N$^{\circ}$ 26, pag. 5149-52, 1996. – Felix Marin Oct 6 '16 at 23:07
• @LinAlg Duoduoduo suggested changing the appearance of 0 to 1, while based on Lesser Cartographies discussion, I need t to be 1 because I am interested in the traditional Traveling Salesman Problem where he visits every other city only once. Is the fix for the current formulations to add the sixth constraints involving the t variable and set t to 1? – Nyxynyx Oct 6 '16 at 23:10
• That is indeed one way to fix this formulation. However, I'm not sure if this is the most efficient formulation. A quick Google search on "mixed integer tsp subtour" shows more commonly used (or taught) formulations. – LinAlg Oct 7 '16 at 0:36

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