Travelling salesman - Linear Programming

Question

So I just asked this question and accepted an answer, but I realized that I still don't understand this, and I can't access my previous question. We have the travelling salesman 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}$

The last constraint, $u_i-u_j +nx_{ij} \le n-1$ makes sure that there are no subtours. However, I don't see what this is. Wikipedia says the following:

To prove that every feasible solution contains only one closed sequence of cities, it suffices to show that every subtour in a feasible solution passes through city 0 (noting that the equalities ensure there can only be one such tour). For if we sum all the inequalities corresponding to $x_{ij}=1$ for any subtour of $k$ steps not passing through city 0, we obtain: $nk \leq (n-1)k$.

I don't understand this at all. How is the $nk \leq (n-1)k$ obtained? And how does this prevent there being any subtours at all? I have no clue.

As for the dummy variables, what purpose do they serve? Wikipedia says:

It now must be shown that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

But it doesn't at all explain why these dummy variables are necessary and what they add to the inequality. I'm stumped.

This question has been asked before here (but the answer doesn't help me at all) and here (by me, I thought it helped but it didn't), but none of the answers help and my question is slightly different, mostly focusing on how they obtained the expression $nk \leq (n-1)k$ and why this prevents subtours from forming

Answer 1

For your first question: suppose you have a solution to the linear program that has subtour $1 \to 2 \to 3 \to 1$. By assumption, the last set of inequalities holds, so if you add up the following, \begin{align} u_1-u_2 + n x_{12} &\le n-1\\ u_2-u_3 + n x_{23} &\le n-1\\ u_3-u_1 + n x_{31} &\le n-1, \end{align} you get $$3n \le 3(n-1).$$ This is a contradiction, so this subtour $1 \to 2 \to 3 \to 1$ does not exist.

In general for any subtour of length $k$ not including $0$, the same argument applies: adding up the inequalities corresponding to each edge of the subtour will give $kn \le k(n-1)$ because the $u_i$ terms will cancel.