4
$\begingroup$

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, that are frequently discussed in the community, like this, this, and this.

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?
$\endgroup$
3
  • $\begingroup$ I think the DFJ constraint can be formulated for directed and undirected graphs. It just says that at least one of the edges must be picked that have one endpoint in S and one outside of S. It does not matter whether this edge is directed or not. The MTZ formulation I am not sure how to formulate this for undirected graphs since it explicitly uses the direction of edges. $\endgroup$ Oct 29, 2021 at 7:30
  • $\begingroup$ @DanielJunglas, Thanks so much. The main issue is that the formulation I have seen to define TSP on the symmetric graph is based on 2-matching constraints and DFJ SEC. Almost, in the lots of optimization software. Would you say please, what you mentioned in the second part (The MTZ formulation I am not sure ...) is separate from how one would model the TSP? (I mean it is general and does not depend on the specific problem)? $\endgroup$
    – A.Omidi
    Nov 1, 2021 at 11:43
  • $\begingroup$ Cross Posted on Math.SE: The difference between subtour-elimination constraints in the symmetric and asymmetric TSP $\endgroup$ Aug 9, 2022 at 18:13

1 Answer 1

1
$\begingroup$

I would like to add an answer by @Misha Lavrov:

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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