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

Have a look at the paper A branch-and-cut algorithm for the capacitated profitable tour problem by Jepsen et al. for more cuts and separation details. It is for the undirected case but can be modified for the directed case.

• I have $|V| = 600$ and $|D| = 20$(destination) then $\forall S \subset V$, will it be possible to compute all subset?
– ooo
Commented Feb 27, 2020 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. Commented Feb 27, 2020 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
Commented Feb 28, 2020 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" Commented Feb 28, 2020 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
Commented Feb 28, 2020 at 15:29