Subtour elimination constraint in Travelling Salesman Problem

Question

I am trying to understand travelling salesman problem, the Dantzig, Fulkerson, Johnson(1954) formulation. In the general formulation given below I am having trouble to implement subtour elimination in a practical problem.

$Min $$\sum\sum c_{ij}x_{ij}$

$s.t.\sum x_{ij}=1, j=1,...,n$

$\sum x_{ij}=1, i=1,...,n$

$\sum\sum x_{ij}\leq|S|-1, \forall i,j,i\neq j$

So I have a simple symmetric problem as the following: \begin{bmatrix} 0 & 3 & 1 & 2 & 4\\ 3 & 0 & 3 & 6 & 7\\ 1 & 3 & 0 & 7 & 4\\ 2 & 6 & 7 & 0 & 1\\ 4 & 7 & 4 & 1 & 0 \end{bmatrix}

I have formulated as the following:

$Min 3x_{12}+x_{13}+2x_{14}+4x_{15}+....+4x_{35}+x_{45}$

$s.t. x_{11}+x_{21}+...+x_{51}=1$

...

$x_{15}+x_{25}+...+x_{55}=1$

$x_{11}+x_{12}+...+x_{15}=1$

...

$x_{51}+x_{52}+...+x_{55}=1$

I have written until here without any problem. But for the last constraint, I couldn't understand how to write it down. How do I add the subtour elimination constraint in the formulation? The following one, to be specific: $\sum\sum x_{ij}\leq|S|-1, \forall i,j,i\neq j$

Answer 1

I think one of the reasons you have difficulties implementing the constraint is because it is not written correctly. You need to be more precise with your indexes. If $N:=\{1,...,n \}$, you can write the constraint as follows: $$ \sum_{i \in S}\sum_{j \in S, j\neq i} x_{ij} \le |S| -1 \quad \forall S \subset N, 2 \le |S| \le n-1 $$

This means that you have to consider all possible subsets $S$ of $N$, and unfortunately there is an exponential number of them. So writing all of them is not really an option.

What you can do is run the program without the constraint, check if you have a subtour, and if you do, dynamically add the cut that forbids this subtour in the following iteration. This is called a lazy constraint, check out Paul Rubin's article.

So for example, if you have the subtour $1-2-1$ (that is, $S=\{1,2\}$), you can add the constraint: $$ \sum_{i \in \{1,2\}}\sum_{j \in \{1,2\}, j\neq i} x_{ij} \le |S| -1 $$ which simplifies to: $$ x_{12}+x_{21} \le 1 $$

Also note that there are different versions of the subtour elimination constraint, such as: $$ \sum_{i \in S}\sum_{j \not \in S} x_{ij} \ge 1 \quad \forall S \subset N, S \neq \emptyset $$ In this version, the constraint imposes that you need at least one edge between two subtours. So with the same above example, you would have: $$ x_{13}+ x_{14}+ x_{15}+ x_{23}+ x_{24} + x_{25} \ge 1 $$ It would be interesting to see which one performs best, I have been told that the second option is better in practice, but I cannot prove it nor have the evidence to confirm it. If anyone has this information, I would love to know about it!

Answer 2

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