Travelling salesman problem as an integer linear program

Question

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear problem:

Label the cities with the numbers $0, ...,n$ and define:

$x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases} $

For $i = 0, ...,n$, let $u_i$ be an artificial variable, and finally take $c_{ij}$ to be the distance from city $i$ to city $j$. Then TSP can be written as the following integer linear programming problem:

$\begin{align} \min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\ & 0 \le x_{ij} \le 1 && i,j=0, \cdots, n \\ & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\ & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\ & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\ &u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n \end{align}$

I don't understand the final constraint, $u_i-u_j +nx_{ij} \le n-1,1 \le i \ne j \le n $. There is a section on wikipedia explaining that this constraint enforces that there is only a single tour covering all cities, instead of multiple disjointed tours covering all cities. It also explains why (see explanation here) but I don't understand that explanation.

Can someone explain how this constraint enforces that there is only a single tour covering all cities?

Answer 1

Consider the case with 4 cities: Albany, Boston, Charlotte, and Detroit.

Thus, one could make a tour that goes from Albany to Boston and back as well as Charlotte to Detroit and back. In this case, each city is an arrival exactly once and is a departure exactly once which satisfies the constraints but isn't a real solution since it isn't a cycle in the graph. (Thus, let's say that Albany to Boston is step 1, Boston to Albany is step 2, Charlotte to Detroit step 3 and Detroit to Charlotte step 4.)

In choosing $u_i=t$ when city $i$ is visited at step $t$ this would make $u_1=1$, $u_2=2$,$u_3=3$ and $u_4=4$.

The 4 $x_{ij}$ that are one are $x_{12},x_{21},x_{34},x_{43}$. Now, consider how this line:

$u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1$

If we swap the $i$ and $j$ here, then the expression would be $t+1-t+n=n+1$ which violates the constraint for the solution noted above and prevents the backtracking which is one way to see this constraint in the problem.

While this may not be an exhaustive answer, hopefully it does provide an idea of why it would work.