# 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. Commented Oct 6, 2016 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? Commented Oct 6, 2016 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. Commented Oct 6, 2016 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? Commented Oct 6, 2016 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. Commented Oct 7, 2016 at 0:36

I have a hunch on whoever made the figure was simultaneously thinking about it in a programming sense (where indexes start at zero) and mistranslated it into a formal expression. A safer way to represent the problem while trying to avoid hard indexes is to use generalizations like so:

Let $$C$$ denote the set of cities that will be visited.

Let $$c_{ij}$$ denote the cost it takes for the traveling salesperson to go from city $$i$$ to city $$j$$.

Let $$x_{ij}$$ denote a binary decision variable if a path from city $$i$$ to city $$j$$ is selected.

then the model will go as follows (Miller-Tucker-Zemlin):

Minimize the cost of traveling to all cities in set $$C$$:

$$\min z = \sum_{i\in C}\sum_{j\in C}c_{ij}x_{ij}$$

Subject to:

Each City needs to be visited: $$\sum_{j\in C} x_{ij}=1\quad\forall i\in C$$ $$\sum_{i\in C} x_{ij}=1\quad\forall j\in C$$

No self loops: $$x_{ii} =0 \quad\forall i\in C$$

Sub-tour Elimination:

$$|C|\cdot x_{ij}+ u_i - u_j \le |C| - 1\quad\forall i \neq j \in\{2,3,\ldots, |C|\}$$ $$1\le u_i \le |C| -1 \quad \forall i \in\{2,3,\ldots, |C|\}$$

Variable Restrictions: $$x_{ij}\in\{0,1\} \quad \forall i,j \in C$$ $$u_i \in \mathbb Z^+ \quad \forall i \in\{2,3,\ldots, |C|\}$$

With this approach, it translates better to the reader what each part is doing in less terms and avoids messy indexing. Also regardless, both of the formulations shown in the question are missing constraints regarding self loops ($$x_{ii} = 0$$)

#### Example: LP Formulation of TSP

Consider the following distance-matrix of 4-Cities TSP:

Exclude the the Diagonal Variables ($$X_{11}, X_{22}, X_{33}, X_{44}$$) from the Distance Table as shown above via zeros.

The following table represents the Assignment Model + the Additional Constraints resulting from $$u_i – u_j + nx_{ij} \le n-1$$; where $$i,j = 2, \cdots, n$$ and i ≠ j.

When n = 4, then,

$$u_i– u_j + nx_{ij} \le 3; \text{ where } i,j = 2, . ., n \text{ and } i ≠ j$$

Then,

$$4x_{23} + u_2 – u_3 \le 3, (i = 2, j = 3)$$ $$4x_{24} + u_2 – u_4 \le 3, (i = 2, j = 4)$$ $$4x_{32} + u_3 – u_2 \le 3, (i = 3, j = 2)$$ $$4x_{34} + u_3 – u_4 \le 3, (i = 3, j = 4)$$ $$4x_{42} + u_4 – u_2 \le 3, (i = 4, j = 2)$$ $$4x_{43} + u_4 – u_3 \le 3, (i = 4, j = 3)$$

V’s X12 X13 X14 X21 X23 X24 X31 X32 X34 X41 X42 X43 U2 U3   U4
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

OF  13  21  26  10  29  20  30  20  5   12  30  7


The associated LP consists of the Assignment Model + the Additional Constraints.

$$\text{Minimize } z = 13X_{12} + 21X_{13} + 26X_{14} + 10X_{21} + 29X_{23} + 20X_{24} + 30X_{31} + 20X_{32} + 5X_{34} + 12X_{41} + 30X_{42} + 7X_{43}$$ Subject to: $$X_{12} + X_{13} + X_{14} = 1$$ $$X_{21} + X_{23} + X_{24} = 1$$ $$X_{31} + X_{32} + X_{34} = 1$$ $$X_{41} + X_{42} + X_{43} = 1$$

$$X_{21} + X_{31} + X_{41} = 1$$ $$X_{12} + X_{32} + X_{42} = 1$$ $$X_{13} + X_{23} + X_{43} = 1$$ $$X_{14} + X_{24} + X_{34} = 1$$

$$4X_{23} + U_2 - U_3 \le 3$$ $$4X_{24} + U_2 - U_4 \le 3$$ $$4X_{32} - U_2 + U_3 \le 3$$ $$4X_{34} + U_3 - U_4 \le 3$$ $$4X_{42} - U_2 + U_4 \le 3$$ $$4X_{43} - U_3 + U_4 \le 3$$

$$U_2, U_3, U_4 \in \Bbb Z^{+}$$ $$x_{ij} \in \{0,1\}, \text{ }\forall ij \in [1,4]$$

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


Therefore, the route is:

$$X_{12} – X_{23} – X_{34} – X_{41} = 59$$