# TSP subtour elimination with multiple formulations

Referring to the question here.

Given a set $$S$$, which we need to travel following TSP rules.

I was wondering if this sub tour elimination method is good enough or not?

Let $$b_{i,j}$$ denote edge from $$i$$ to $$j$$ is taken or not and $$d_{i,j} > 0$$ denotes distance from $$i$$ to $$j$$.

\begin{align}\min&\quad\sum_{i,j \in S} d_{i,j} \cdot b_{i,j}\\\text{s.t.}&\quad\sum_{j \in S} b_{j,i} - \sum_{k \in S} b_{i,k} = 0\\&\quad\sum_{j \in S} b_{j,i} = 1\end{align}

Let $$s_0$$ be the start node. Now use a continuous variable $$DS_i$$ to store the distance at node $$i$$, with $$DS_{s_0} = 0$$.

$$\forall j \in S \setminus \{s_0\} \quad DS_{j} = \sum_{i} b_{i,j} \cdot (DS_{i} + d_{i,j})$$

The last constraint eliminates the sub-tour in the path and is similar to MTZ formulation as per the answer given.

In order to speed up the solver, I created a call back where I am trying to eliminate the sub tour, but the problem is due to the last constraint (MTZ equivalent) call back is not getting any sub tour to detect as it is already solved by the last constraint (MTZ equivalent), so the speed is slow.

Here is the log at callback with the last constraint ON:

The total number of nodes = 9.

--> lazy constraint callback called: #1
[0, 4, 1, 6, 2, 5, 8, 7, 3, 0]
--> lazy constraint callback called: #2
[0, 6, 3, 4, 8, 7, 5, 2, 1, 0]
--> lazy constraint callback called: #3
[0, 3, 6, 4, 7, 8, 5, 2, 1, 0]


Here is the log at callback with the last constraint OFF:

The total number of nodes = 9.

--> lazy constraint callback called: #1
[0, 1, 2, 0]
--> lazy constraint callback called: #2
[0, 2, 1, 0]
--> lazy constraint callback called: #3
[0, 1, 2, 5, 8, 7, 4, 3, 6, 0]

• There are some related posts in ORSE. For instance this or this. Also, if you are interested to use the lazy callback to eliminate sub-tours you will find good examples on solvers host, like Gurobi. – A.Omidi Mar 10 '20 at 6:50
• My current implementation has DFJ in a lazy callback way, but I am not sure if I add my MTZ equivalent constraint as normal constraint, performance will be equal to MTZ as now callbacks have no sub tours. – ooo Mar 10 '20 at 7:09
• Would you try using others sub-tour elimination as described in attached file on the above link? – A.Omidi Mar 10 '20 at 8:34
• I have edited my question now I hope now I am clear. – ooo Mar 10 '20 at 10:12