7
$\begingroup$

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

Subtours

$\endgroup$
0

4 Answers 4

10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.