1

I am trying to understand travelling salesman problem, the Dantzig, Fulkerson, Johnson(1954) formulation. In the general formulation given below I am having trouble to implement subtour elimination in a practical problem.

$Min $$\sum\sum c_{ij}x_{ij}$

$s.t.\sum x_{ij}=1, j=1,...,n$

$\sum x_{ij}=1, i=1,...,n$

$\sum\sum x_{ij}\leq|S|-1, \forall i,j,i\neq j$

So I have a simple symmetric problem as the following: \begin{bmatrix} 0 & 3 & 1 & 2 & 4\\ 3 & 0 & 3 & 6 & 7\\ 1 & 3 & 0 & 7 & 4\\ 2 & 6 & 7 & 0 & 1\\ 4 & 7 & 4 & 1 & 0 \end{bmatrix}

I have formulated as the following:

$Min 3x_{12}+x_{13}+2x_{14}+4x_{15}+....+4x_{35}+x_{45}$

$s.t. x_{11}+x_{21}+...+x_{51}=1$

...

$x_{15}+x_{25}+...+x_{55}=1$

$x_{11}+x_{12}+...+x_{15}=1$

...

$x_{51}+x_{52}+...+x_{55}=1$

I have written until here without any problem. But for the last constraint, I couldn't understand how to write it down. How do I add the subtour elimination constraint in the formulation? The following one, to be specific: $\sum\sum x_{ij}\leq|S|-1, \forall i,j,i\neq j$

madetolast
  • 123

1 Answers1

1

I think your subtour elimination constraint may be incomplete. I believe the Dantzig, Fulkerson, Johnson(1954) algorithm imposes the following constraint to disallow any local tours.

For all subsets $ S \subseteq \{1,...,n \}$, $ 1 \leq |S| \leq n-1 $, $$ \sum_{i,j \in S, i \neq j} x_{ij} \leq |S|-1. $$

With this all you have to do is consider all subsets $S$ and add the following constraints to your problem. $$ x_{12} + x_{21} \leq 1 \hspace{2cm}(S = \{1,2\}) $$ $$x_{13} + x_{31} \leq 1 \hspace{2cm}(S = \{1,3\}) $$ $$ \vdots $$ and so on. Notice that you should have $ \sum_{2 \leq i \leq n-1}\binom{n}{i}$ such constraints. Hope this helps.

av13
  • 31