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.

My question is how efficient this sub tour elimination constraint is and how to calculate it.


My understanding is that you effectively mimic the Miller, Tucker, Zemlin style of subtour elimination constraints by "pushing a counter along the tour", these are reportedly not the computationally strongest formulations.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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