# TSP on a non-complete graph

I have a non-complete graph $$G$$ with $$V$$ vertices and a set $$D \subset V$$ that needs to be traveled by a vehicle and then return to source at last.

Binary variables $$b_{i,j}$$ represent if the edge $$(i,j)$$ is taken or not. $$G_{i,j}$$ represent the distance between node $$i$$ and node $$j$$.

$$\min \sum_{i,j\in V}b_{i,j} \cdot G_{i,j}$$

Below 2 constraints eliminate loops:

$$\sum_{j\in V}b_{i,j} \leq 1$$

$$\sum_{j\in V}b_{j,i} \leq 1$$

The following constraint ensures that there are only one incoming and one outgoing edges for each node.

$$\sum_{j\in V}b_{j,i} - \sum_{j\in V}b_{i,j} = 0 \ \ \ \forall j \in V$$

Below constraint ensures that all the nodes in $$D$$ must be visited.

$$\sum_{j\in V}b_{j,i} = 1 \ \ \ \forall i \in D$$

MTZ. constraint: $$\forall (i,j) \in V$$ and $$(i,j) \neq D_0$$, i.e., starting node.

$$U_i - U_j + |V| \cdot b_{i,j} \leq |V| - 1$$

The problem with this model is, it is slow, I am looking for some ways to make it faster.

The reason I am not able to apply Danzig-Fulkerson-Johnson formulation is that the size of $$V = 72$$ so creating all subset is not possible. Another way of doing it is to create a complete graph for $$D$$ and then apply Danzig-Fulkerson-Johnson but I need to know the nodes that are used to reach nodes in set $$D$$ that's why I can't create complete graph also there are other constraints that can change the route to reach nodes in set $$D$$.

I have also tried Desrochers-Laporte formulation but there is no significant difference.

My question is:

Is there any way to use Danzig-Fulkerson-Johnson formulation in this or some other way to solve the problem faster.

You are solving a kind of a shortest path problem so you could add a generalized version of the subtour elimination constraints as $$\sum_{(i,j) \in \delta^+(S)} b_{ij} \geq \sum_{(k,j) \in \delta^+(k)} b_{kj}, \; \forall k \in S, \forall S \subseteq V, |S| \geq 2$$ where $$\delta^+$$ represents the outgoing edges of a set of nodes. Alternatively as $$\sum_{(i,j) \in E(S)} b_{ij} \leq \sum_{i \in S\setminus (k)} \sum_{(i,j) \in \delta^+(i)} b_{ij}, \; \forall k \in S,\forall S \subseteq V, |S| \geq 2$$ with $$E(S)$$ being the edges within the node set $$S$$.
• I have $|V| = 600$ and $|D| = 20$(destination) then $\forall S \subset V$, will it be possible to compute all subset? – ooo Feb 27 '20 at 13:21
• You can find the most violating subtour by solving a minimum (s,t)-cut for each node $s \in V\setminus(t)$ for a $t \in D$. Edge weights are the fractional values of the edge variables. I think enumeration of all subsets would take too long and you would create a massive amount of non-binding constraints. – Simon Spoorendonk Feb 27 '20 at 14:45
• OK, I have a set D = [2,3,5,4,2] now after performing mincut on (2,3), (2,5) ..., (3,5), (3,4) ..., I get a set of mincut edges E = [(6,9), (8,10), ...]. Now I am confused what to do next. – ooo Feb 28 '20 at 5:25
• From the endpoints of the mincut edges you get $S$ and $V \setminus S$. Just saw that Wolsey have an example at p. 155 in "Integer Programming" – Simon Spoorendonk Feb 28 '20 at 7:51
• So what I have understood till now is that from the edges of mincut I should pick their endpoints and create a set $S$ and apply DFJ formulation but take only those subsets that contain one of the nodes from set $S$.OR I can just add constraints enforcing that some of the edges from the mincut edge set needs to be taken. Correct me if I am wrong. – ooo Feb 28 '20 at 15:29