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
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  &lt;=  n-1; i,j = 2, . ., n &amp; i ≠ j

n = 4
ui  – uj + n xij  &lt;=  3; i,j = 2, . ., n &amp; i ≠ j

n xij + ui  – uj  &lt;=  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 &lt;= 3
C10 4X24 + 1U2 - 1U4 &lt;= 3
C11 4X32 - 1U2 + 1U3 &lt;= 3
C12 4X34 + 1U3 - 1U4 &lt;= 3
C13 4X42 - 1U2 + 1U4 &lt;= 3
C14 4X43 - 1U3 + 1U4 &lt;= 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
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  &lt;=  n-1; i,j = 2, . ., n &amp; i ≠ j

n = 4
ui  – uj + n xij  &lt;=  3; i,j = 2, . ., n &amp; i ≠ j

n xij + ui  – uj  &lt;=  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 &lt;= 3
C10 4X24 + 1U2 - 1U4 &lt;= 3
C11 4X32 - 1U2 + 1U3 &lt;= 3
C12 4X34 + 1U3 - 1U4 &lt;= 3
C13 4X42 - 1U2 + 1U4 &lt;= 3
C14 4X43 - 1U3 + 1U4 &lt;= 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