3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ would you see this link? $\endgroup$ – A.Omidi Feb 5 at 10:54
  • 2
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 Feb 5 at 13:18
  • $\begingroup$ 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$ $\endgroup$ – anoop Feb 5 at 14:26
  • 1
    $\begingroup$ Your problem looks like shortest path more than a TSP... I agree with @LarrySnyder610 $\endgroup$ – Oguz Toragay Feb 5 at 14:46
  • $\begingroup$ 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$ $\endgroup$ – anoop Feb 5 at 14:54
7
$\begingroup$

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'$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – anoop Feb 5 at 16:40
  • $\begingroup$ 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? $\endgroup$ – rowtricker Feb 5 at 17:00
  • $\begingroup$ 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 $\endgroup$ – anoop Feb 5 at 17:05
  • $\begingroup$ 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. $\endgroup$ – rowtricker Feb 5 at 17:20
  • $\begingroup$ 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. $\endgroup$ – anoop Feb 5 at 17:58

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.