The difference between subtour-elimination constraints in the symmetric and asymmetric TSP

Question

We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, there exist two well-known subtour-elimination constraints (SECs), MTZ and DFJ, and also whose variants, that are frequently used.

But in order to SECs and whose dependency on the defined graph, I have some questions. I was wondering if,

1. Is there any classification to figure out which one belongs to which graph?
2. Is it possible to define directed graph-based SECs on the undirected ones? for example, The MTZ formulation is defined on the directed and DFJ defined on the undirected. Might be it changed vise versa?
3. What is the difference between graph symmetry and traveling cost symmetry? or they have the same mean?

Answer 1

The MTZ constraints really need to know the direction of an edge in order to work. I have called them "timing constraints" when teaching, because they are an inequality representation of the condition

If $x_{ij} = 1$ (if we go from vertex $i$ to vertex $j$) then $t_j$ (the MTZ variable that intuitively means "the time at which we visit vertex $j$") is at least $t_i + 1$ (we visit $t_j$ later than $t_i$). In particular, $t_j > t_i$.

This constraint is skipped for the starting vertex, which is also the ending vertex. But there cannot be a cycle not containing that vertex, because we can't have $t_a < t_b < t_c < \dots < t_k < t_a$.

If we do not know the orientation that $x_{ij}$ indicates, then we can't enforce this constraint. Also, it wouldn't be enough to ask "$t_j \ge t_i + 1$ or $t_i \ge t_j + 1$" even if we could ask that, because then you could have an even cycle that alternates between time $1$ and time $2$.

---

The DFJ constraints are going to be fine no matter what. In a directed formulation, for any vertex set $S$ not equal to $V$ or the empty set, we have $$ \sum_{i \in S} \sum_{j \notin S} x_{ij} \ge 1 \qquad \sum_{i \notin S} \sum_{j \in S} x_{ij} \ge 1 $$ and just having one of these is sufficient (they break the same subtours, and in fact given the starting constraints of the TSP, either implies the other). In an undirected formulation, we could use either one just fine, or we could technically increase the RHS to $2$ (because any tour must leave $S$ and come back, so there's at least $2$ crossing edges).

---

Regarding graph symmetry and traveling cost symmetry: essentially, these are the same in the traveling salesman setting, since we assume all edges exist and just give them a very high cost if we don't want them to be used. The distinction you need to be aware of is that even if your traveling costs are symmetric ($c_{ij} = c_{ji}$) you may choose to go with a directed graph formulation of the problem (for example, if you really want to use the MTZ constraints).