5
$\begingroup$

In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is easy to accomplish as if there is no straight path between A and B, we can simply assign a new edge whose length is the shortest path between A and B.

However, if we have a sparse graph, maybe we can benefit from not having a complete graph. In this case, we might be forced to repeat vertices. If our graph is only 3 cities, and only two edges, connecting (1, 2) and (2, 3), then the solution must repeat city 2: 1 - 2 - 3 - 2 - 1.

I am struggling to find examples of TSP in the scientific literature which assume a non complete directed graph. Any known references? Any keywords I may be missing? In this case, cycles are allowed.

I am especially interested in how we could separate subtour inequalities when cycles are present. I am hoping for a solution based on integer linear programming and branch-and-bound, and am wondering how to add subtour elimination inequalities. Any ideas?

$\endgroup$
  • $\begingroup$ Reference: mathworld.wolfram.com/All-PairsShortestPath.html $\;$ $\endgroup$ – user12859 Jun 19 '15 at 4:24
  • 1
    $\begingroup$ Can't you reduce this to the usual TSP? If two nodes are not connected, add an edge with weight according to the shortest path between the nodes. Solve TSP, translate all added edges into their resp. paths. $\endgroup$ – Raphael Jun 19 '15 at 9:20
  • $\begingroup$ Hi Raphael, that is precisely what I want to avoid. I have a very sparse graph and, actually, my problem is not really the TSP (not all cities must be visited), although this is not important for this example. $\endgroup$ – Chicoscience Jun 19 '15 at 12:01
  • $\begingroup$ Since the number of edges in the graph does not influence the complexity of the problem all too much: why? (With this reduction, you can even throw away all the nodes you don't have to visit.) If space is the issue, you can leave the edges implicit and (re)compute their weights by solving SSSPP every time you need them (or cache only some). $\endgroup$ – Raphael Jun 19 '15 at 12:03
  • 1
    $\begingroup$ I'm not entirely sure what you are trying to optimize. What objective function are you trying to minimize? Are you trying to minimize the total path length, and you don't care about how many vertices have to be repeat-visited? Are you trying to minimize the number of repeat-visits, without regard to total path length? Or some combination of these two metrics? $\endgroup$ – D.W. Jun 19 '15 at 17:40
4
$\begingroup$

This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and $C$, the distance from $A$ to $B$ is no greater than the distance from $A$ to $C$ to $B$.

As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the distance from $A$ to $B$ to be the length of the shortest $A$–$B$ path in the original graph. This shows that your problem is no harder than metric TSP. But, conversely, every instance of metric TSP is already an instance of your problem. This is because, in metric TSP, the triangle inequality guarantees that it's never necessary to revisit a vertex so allowing revisiting doesn't change the optimal solution.

$\endgroup$
  • $\begingroup$ Dear David, thanks for the answer, but unfortunately that is exactly what I wanted to avoid. I even mentioned the same technique (shortest $AB$ path) in the original question. I have a very very sparse and large graph, and completing with all edges is something I wish to avoid (at least give it a try). I know how to separate subtour constraints when cycles are not allowed (min cut / max flow algorithm), but not when cycles are allowed. $\endgroup$ – Chicoscience Jun 19 '15 at 12:03
  • 1
    $\begingroup$ @Chicoscience Unless you can quantify the sparseness, I've just shown that the problem is as hard as general metric TSP. Without more information, it is, in a sense, impossible to avoid this solution. $\endgroup$ – David Richerby Jun 19 '15 at 14:00
  • 1
    $\begingroup$ From a complexity theory perspective, this reasoning is interesting and valid. However, I'm not sure it answers the OP's question. The OP is dealing with a sparse graph. The reduction from metric TSP to his problem does not take this into account: it does not output a sparse graph. And, from a pragmatic perspective, it doesn't really seem to rule out the possibility that there might be algorithms that are more efficient for his case (with a sparse graph) than the best algorithms for standard metric TSP. So: interesting, for sure, but maybe not the end of the story. $\endgroup$ – D.W. Jun 19 '15 at 17:44
  • 1
    $\begingroup$ It's not hard to quantify sparseness. For instance, one simple way to quantify sparseness would be: consider graphs where $|E| \le c \cdot |V|$, where $c$ is some fixed constant. In a comment, the OP mentions he usually has $|E| \le 4 |V|$ in his application. $\endgroup$ – D.W. Jun 19 '15 at 17:46
3
$\begingroup$

I actually found this solution some time ago, but here we go. This is a formulation in a directed graph that can repeat vertices and does not repeat arcs. It requires that for every arc $(i,j)$ there exists an arc $(j,i)$, and that the distance $d_{ij} = d_{ji} \geq 0$.

We deal with a directed graph $G = (V, A)$. For $W \subseteq V$, we define $\delta^-(W) = \{ (i,j) \in A: i \not \in W, j \in W\}$, $\delta^+(W) = \{ (i,j) \in A: i \in W, j \not \in W\}$ and $A(W) = \{ (i,j) \in A: i \in W, j \in W\}$.

We are looking for, in graph terminology, a closed walk that covers all vertices (a walk may contain cycles).

The decision variables are:

$x_{ij} = 1$ if arc $a_{ij}$ is in the walk, $0$ otherwise (binary variable)

$g_{i} = $ the outdegree of vertex $i$ (continuous variable)

The formulation is given by:

$$ \min \sum_{(i,j) \in A} d_{ij} x_{ij} $$

subject to:

$$ \sum_{(i,j) \in \delta^+(i)} x_{ij} = g_i, \;\;\;\;\forall i \in V $$ $$ \sum_{(i,j) \in \delta^+(i)} x_{ij} = \sum_{(j,i) \in \delta^-(i)} x_{ji}, , \;\;\;\;\forall i \in V $$ $$ \sum_{(i,j) \in \delta^+(i)} x_{ij} \geq 1, \;\;\;\;\forall i \in V $$ $$ \sum_{i \in W} g_{i} \geq 1 + \sum_{(i,j) \in A(W)} x_{ij} , \;\;\;\; \forall W \subsetneq V, |W| > 1 $$

These last constraints are subtour elimination constraints, which can be expressed in a nice manner thanks to the $g_i$ linear variables. The separation of these constraints is actually polynomial, as it can be solved using a maxflow algorithm.

Notice that for every subset of vertices $W$, $\sum_{i \in W} g_{i} - \sum_{(i,j) \in A(W)} x_{ij} \geq 1$. The 1 in this constraint means that at least one vertex must leave $W$.

Given a solution to a linear relaxation represented by $\overline{g}_i$ and $\overline{x}_{ij}$, we need to find $W$ that minimises the expression $\sum_{i \in W} \overline{g}_{i} - \sum_{(i,j) \in A(W)} \overline{x}_{ij}$.

Solving this problem is equivalent to finding $W$ which is separated from the rest of the graph (given any vertex being source and sink) by a minimum cut, which is equivalent to the max flow. If the max flow value is less than 1, we found a violated cut and we can add it to the model.

$\endgroup$
  • $\begingroup$ can you please post the source where you find the solution you have provided $\endgroup$ – K.Saeed Sep 4 '17 at 10:33
  • $\begingroup$ Look for the Graphical TSP in literature. Some important works are Ratcliff and Rosenthal (1983), Fleischmann (1988) and other works by Naddef, Nachef, Cornuejols and Letchford. $\endgroup$ – Chicoscience Sep 8 '17 at 2:29

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.