Interpretation of a subtour elimination constraint in the TSP

Question

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$.

Answer 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$.

Answer 2

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

Answer 3

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.

Answer 4

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