# Interpretation of a subtour elimination constraint in the TSP

I have a problem with understanding the following mathematical model of the TSP. Given that the TSP is:

$$\min \sum_{i,j\in N} d_{i,j} \cdot x_{i,j}$$

subjected to:

$$\begin{array}{rrrr}\sum_{j\in N}x_{i,j}&=&1&\forall i \in N\\\ \sum_{i\in N}x_{i,j} &=& 1 & \forall j \in N\\ u_{i}+1 &\leq& u_{j} + |N| \cdot (1-x_{i,j})&\forall i,j \in N: i\neq j, j\neq 1\\ u_{1} &=& 1& \forall i \in N \\ x_{i,i} &=& 0 &\forall i \in N \\ x_{i,j} &\in& \{0,1\}&\forall i,j \in N\\ u_{i} &\in& \mathbb{Z}_{+} &\forall i \in N\end{array}$$

Where $$x_{i,j}$$ is an integer, that determines whether the path is selected in the solution and $$u_{i}$$ is the position of city $$i$$ along the tour. $$N$$ is a set of cities and $$d_{i,j}$$ is the distance between city $$i$$ and $$j$$.

I have a hard time understanding the constraint $$u_{i} + 1 \leq u_{j} + |N| (1-x_{i,j})$$. I do not see the inuition behind, why this constraint would eliminate the subtours. Suppose, I have three tours (see in the figure below). The left circle is a solution to the TSP, while the right one is one with only the subtours. I am not sure how the constraint would prohibit a subtour from forming, as $$|N|$$ seems to be big enough to allow for subtours if my $$u_{j} = 1$$. These constraints are called Miller-Tucker-Zemlin (MTZ) constraints, you can find a lot of technical notes online.

They impose that a node can only be visited once. You can think of the $$u_i$$ variables as the order of the sequence of the visits. Every time $$x_{ij}=1$$, the order variable is incremented by one unit.

Consider a subtour $$A-B-A$$. You have $$x_{AB}=x_{BA}=1$$. But with the MTZ constraints, without loss of generality, if $$u_A=1$$, then necessarily, $$u_B\ge 2$$. And so you cannot have $$u_B +1 \le u_A$$, which contradicts $$x_{BA}=1$$.

To add another answer that focuses on why we use $$\vert N\vert$$ in the constraint:

As @Pedrinho @Kuifje stated, the $$u_i$$ variables can be interpreted as the order of city $$i$$ in the tour. That is, $$u_i=k$$ means that city $$i$$ is number $$k$$ on the tour.

Hence, we know that given $$\vert N\vert$$ cities, we have $$1\leq u_i\leq \vert N\vert$$. Then we want to enforce the constraint $$x_{ij}=1\Rightarrow u_i+1\leq u_j$$ meaning that if we go directly from city $$i$$ to city $$j$$ then city $$j$$ should not be visited before city $$i$$. We can do that with a big-$$M$$ constraint $$\begin{equation} u_i+1-u_j\leq M(1-x_{ij}) \Leftrightarrow u_i-u_j+Mx_{ij}\leq M-1 \end{equation}$$ Now, if $$x_{ij}=1$$, we see that the inequality reduces to $$u_i+1\leq u_j$$ which is what we want. Next, we should find the smallest possible value for $$M$$. To do so, we look at the constraint in case of $$x_{ij}=0$$: $$\begin{equation} u_i-u_j \leq M-1 \end{equation}$$ To find the smallest possible value of $$M$$ we need to make sure that $$u_i-u_j$$ never exceeds $$M-1$$, so we find the largest possible value for $$u_i-u_j$$, which is when $$u_i$$ is as large as possible ($$\vert N\vert$$) and $$u_j$$ is as small as possible ($$1$$). Hence, $$u_i-u_j\leq \vert N\vert-1$$ and we thus know the value of $$M$$, namely $$M=\vert N\vert$$.

Actually, since you know your starting point ($$u_1=1$$), you can strengthen your MTZ constraints slightly by \begin{align} &u_i-u_j + (\vert N\vert -1)x_{ij}\leq \vert N\vert -2,&&\forall i\neq j=2,\dots,\vert N\vert \\ &2\leq u_i\leq \vert N\vert, &&\forall i=2,\dots,\vert N\vert \end{align}

Unfortunately, the MTZ-constraints provide a very weak formulation of the TSP. To see why, you may take a look at the excellent paper "Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?" by Tolga Bektas and Luis Gouveia

The constraint is nicely explained by @Kuifje. I want to add the following point concerning your comment regarding $$|N|$$.

$$|N|$$ is only in place if $$x_{ij} = 0$$, so if there is no connecting edge between $$i$$ and $$j$$.

If $$x_{ij} = 1$$ then the constraint equals $$u_i +1 \leq u_j$$, which prevents subtours as explained by @Kuifje.

A good visualization is in the video https://youtu.be/SzORM1aSwQY