TSP on a non-complete graph

Question

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.

Answer 1

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.