3

I have a graph $G$ and have a set $S$ which are the points in the graph to visit in a TSP manner.

Since the length of the TSP route can't be known as it can use any number of nodes to complete the journey.

I was wondering if it is possible to use Dantzig-Fulkerson-Johnson formulation or only Miller-Tucker-Zemlin formulation can be used.

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
ooo
  • 1,589
  • 4
  • 12
  • would you see this link? – A.Omidi Feb 05 '20 at 10:54
  • 2
    What do you mean "it can use any number of nodes to complete the journey"? The TSP assumes every node is visited exactly once. If you are saying that because it's a graph, so the route from node A to node B might pass through other nodes, then you should just calcualte shortest-path distances ahead of time and treat the path from A-B as a single edge. – LarrySnyder610 Feb 05 '20 at 13:18
  • Let's say I have to visit nodes 2, 8, 23, 29 where the total number of nodes is 100. Then it is similar to TSP. One path can be like $2,$4,7,$8$,16,20,$23$,34,10,$29$ – ooo Feb 05 '20 at 14:26
  • 1
    Your problem looks like shortest path more than a TSP... I agree with @LarrySnyder610 – Oguz Toragay Feb 05 '20 at 14:46
  • But out of 2, 8, 23, 29 I don't know which one to visit first, i.e., order not known. One path can also be like $2$,4,7,$8$,34,10,$29$,16,20,$23$. The source is known $2$ – ooo Feb 05 '20 at 14:54
  • Could you clarify whether the nodes in $V \setminus S$ (i.e. the nodes of the graph not in $S$) can be visited as often as desired, or whether they should be visited at most once in the final solution? Would be allowed in your example to visit node 4 twice, if that results in a better solution? – Paul Bouman Feb 11 '20 at 07:11
  • a node can only be visited once – ooo Feb 13 '20 at 09:15

1 Answers1

7

As suggested by Larry Snyder in the comments to your question, you can reduce your problem to a standard traveling salesman problem by means of precomputing the distances. In particular, consider the complete graph with nodes given by $S$. Moreover, consider as distance between nodes $s_1$ and $s_2$ the shortest path between those nodes in your original graph $G$ (and a distance of $\infty$ if no path exists).

You are now left with a standard traveling salesman problem on which both types of formulations can be used. For some more information on what the best performing formulation would be, see the information in this question. In particular, note that the Dantzig-Fulkerson-Johnson (DFJ) is generally seen as the best performing formulation.

In case the paths between any two nodes in $S$ needs to be determined in the model (while the whole thing should still be a tour), you could adjust the DFJ formulation to account for only having to visit the nodes in $S$. In particular, replace the typical constraints \begin{align} & \sum_{j=1}^{n} x_{ij} = 1 && \forall i \in V,\\ & \sum_{i=1}^{n} x_{ij} = 1 && \forall j \in V,\\ \end{align} by \begin{align} & \sum_{j=1}^{n} x_{ij} = 1 && \forall i \in S,\\ & \sum_{i=1}^{n} x_{ij} = 1 && \forall j \in S,\\ & \sum_{j=1}^{n} x_{ij} = \sum_{j=1}^{n} x_{ji} && \forall i \in V \setminus S. \end{align} Note that these constraints imply that there is again a collection of tours.

As for the regular TSP, it is needed to include subtour elimination constraints. In particular, we want to prevent that there are subtours that include only a subset of the nodes in $S$ (or subtours containing no nodes in $S$). We thus need to add a subtour elimination constraint for each $V' \subset V: S \nsubseteq V'$.

rowtricker
  • 83
  • 4
  • I need to know the path between $s_1$ and $s_2$ because I have some other equations that use these paths and it is not the case that path between $s_1$ and $s_2$ is the shortest it has many factors other than distance. – ooo Feb 05 '20 at 16:40
  • I don't think that any of the two formulations would be directly applicable in that case. However, it depends on your other equations in what way to adjust them. Can you give somewhat more details of these equations? – rowtricker Feb 05 '20 at 17:00
  • You can force an edge to the nodes in $S$ and then apply MTZ with n = size of the graph, but I wanted to know is it possible to apply DFJ – ooo Feb 05 '20 at 17:05
  • It is not entirely clear to me in what way you adjust the MTZ formulation. However, it seems to me that a similar strategy can be used for the DFJ formulation. In essence, ensuring that a tour is created (by preventing any subcycles that do not pass your starting node) by including flow conservation constraints and ensuring there is an in and outflow of 1 of any nodes in $S$. Sub-tour constraints can then still be used to ensure there are no subcycles. – rowtricker Feb 05 '20 at 17:20
  • Problem with DFJ is their sub tour elimination constraint requires a $Q$ set. (from Wikipedia) and it needs to be of the size of the tour whereas in MTZ we can use a larger value of n (again from Wikipedia ). I may be wrong here, and I don't know the size of the tour so I am using MTZ and I want to know can I use DFJ here by any chance. – ooo Feb 05 '20 at 17:58
  • 3 constraint you added, I am using similar constraint and $$\forall i,j \in V \quad u_{i} - u_{j} + n \cdot x_{i,j,} \leq n - 1$$ for subtour elimination I wanted to know if it is poosible to use DFJ. $n = |V|$ – ooo Feb 06 '20 at 13:20
  • See the last edit on how to pick the subtour elimination constraints for the DFJ formulation. – rowtricker Feb 07 '20 at 09:12