# Subtour elimination constraint in Travelling Salesman Problem

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

• There is an introduction to Techniques for Subtour Elimination in TSP: Theory and Implementation in Python on the medium. Would you see that? Apr 24, 2021 at 12:01
• You need to exclude $x_{i,i}$ or the optimal solution has zero cost. For this directed formulation, the objective also needs to include $x_{i,j}$ with $i>j$. Apr 24, 2021 at 13:19

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!

• Is there any resource that I can find mathematical formulations of different algorithms/heuristics created for basic problems? I am using Introduction to Logistics Systems Planning and Control of Ghiani, Laporte and Musmanno. Even though there are such examples for different subjects, in TSP and VRP section only general formulations are given without any guiding example problems. Therefore, I am struggling to connect theory with practice. @A.Omidi Apr 24, 2021 at 13:09
• @madetolast, as far as I know, there are some useful and practical example in the optimization software host like, AMPL, GAMS, CPLEX, Gurobi, etc. Are you looking for? Apr 24, 2021 at 16:39
• Appreciate your response! They are more often focused on coding part, however I am trying to improve on the mathematical modeling. I checked them but some of the examples are not simple enough for me to understand, some of them are simple but they include only complicated codes which I cannot follow. By the way, it kinda looked like I directed my question to only you, but if the other respondents would like to add something I'd love to hear. @RobPratt Apr 24, 2021 at 17:45
• For model formulation (not algorithms or heuristics) I can recommend the book "Model Building in Mathematical Programming" by H. Paul Williams.
– prubin
Apr 24, 2021 at 18:00
• The problems from the Williams book are all described, modeled, and solved here: go.documentation.sas.com/doc/en/pgmsascdc/9.4_3.5/ormpex/… Apr 24, 2021 at 18:28