Problema del viajante de comercio como un programa lineal entero

Entonces, el problema del vendedor ambulante es un problema en el que un vendedor tiene que viajar por todas las ciudades de manera que la distancia total de viaje sea mínima. Puedes reescribir esto como un problema lineal entero:

Etiqueta las ciudades con los números$0, ...,n$y definir:

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

Para$i = 0, ...,n$, dejar$u_i$ser una variable artificial, y finalmente tomar$c_{ij}$ser la distancia de la ciudad$i$a la ciudad$j$. Entonces TSP se puede escribir como el siguiente problema de programación lineal entera:

$\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}$

No entiendo la restricción final,$u_i-u_j +nx_{ij} \le n-1,1 \le i \ne j \le n$. Hay una sección en wikipedia que explica que esta restricción impone que solo haya un único recorrido que cubra todas las ciudades, en lugar de múltiples recorridos inconexos que cubran todas las ciudades. También explica por qué ( ver explicación aquí ) pero no entiendo esa explicación.

¿Alguien puede explicar cómo esta restricción impone que solo haya un solo recorrido que cubra todas las ciudades?