4
$\begingroup$

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.

Improve this question
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I have $|V| = 600$ and $|D| = 20$(destination) then $\forall S \subset V$, will it be possible to compute all subset? $\endgroup$ – ooo Feb 27 '20 at 13:21
  • $\begingroup$ 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. $\endgroup$ – Simon Spoorendonk Feb 27 '20 at 14:45
  • $\begingroup$ 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. $\endgroup$ – ooo Feb 28 '20 at 5:25
  • $\begingroup$ 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" $\endgroup$ – Simon Spoorendonk Feb 28 '20 at 7:51
  • $\begingroup$ 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. $\endgroup$ – ooo Feb 28 '20 at 15:29

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.