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]
Add violated subtour
--> lazy constraint callback called: #2
[0, 2, 1, 0]
Add violated subtour
--> lazy constraint callback called: #3
[0, 1, 2, 5, 8, 7, 4, 3, 6, 0]
