5
$\begingroup$

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$

$\endgroup$
2
  • 1
    $\begingroup$ There is an introduction to Techniques for Subtour Elimination in TSP: Theory and Implementation in Python on the medium. Would you see that? $\endgroup$ – A.Omidi Apr 24 at 12:01
  • 1
    $\begingroup$ You need to exclude $x_{i,i}$ or the optimal solution has zero cost. For this directed formulation, the objective also needs to include $x_{i,j}$ with $i>j$. $\endgroup$ – RobPratt Apr 24 at 13:19
8
$\begingroup$

I think one of the reasons you have difficulties implementing the constraint is because it is not written correctly. You need to be more precise with your indexes. If $N:=\{1,...,n \}$, you can write the constraint as follows: $$ \sum_{i \in S}\sum_{j \in S, j\neq i} x_{ij} \le |S| -1 \quad \forall S \subset N, 2 \le |S| \le n-1 $$

This means that you have to consider all possible subsets $S$ of $N$, and unfortunately there is an exponential number of them. So writing all of them is not really an option.

What you can do is run the program without the constraint, check if you have a subtour, and if you do, dynamically add the cut that forbids this subtour in the following iteration. This is called a lazy constraint, check out Paul Rubin's article.

So for example, if you have the subtour $1-2-1$ (that is, $S=\{1,2\}$), you can add the constraint: $$ \sum_{i \in \{1,2\}}\sum_{j \in \{1,2\}, j\neq i} x_{ij} \le |S| -1 $$ which simplifies to: $$ x_{12}+x_{21} \le 1 $$

Also note that there are different versions of the subtour elimination constraint, such as: $$ \sum_{i \in S}\sum_{j \not \in S} x_{ij} \ge 1 \quad \forall S \subset N, S \neq \emptyset $$ In this version, the constraint imposes that you need at least one edge between two subtours. So with the same above example, you would have: $$ x_{13}+ x_{14}+ x_{15}+ x_{23}+ x_{24} + x_{25} \ge 1 $$ It would be interesting to see which one performs best, I have been told that the second option is better in practice, but I cannot prove it nor have the evidence to confirm it. If anyone has this information, I would love to know about it!

$\endgroup$
5
  • $\begingroup$ Is there any resource that I can find mathematical formulations of different algorithms/heuristics created for basic problems? I am using Introduction to Logistics Systems Planning and Control of Ghiani, Laporte and Musmanno. Even though there are such examples for different subjects, in TSP and VRP section only general formulations are given without any guiding example problems. Therefore, I am struggling to connect theory with practice. @A.Omidi $\endgroup$ – madetolast Apr 24 at 13:09
  • 1
    $\begingroup$ @madetolast, as far as I know, there are some useful and practical example in the optimization software host like, AMPL, GAMS, CPLEX, Gurobi, etc. Are you looking for? $\endgroup$ – A.Omidi Apr 24 at 16:39
  • $\begingroup$ Appreciate your response! They are more often focused on coding part, however I am trying to improve on the mathematical modeling. I checked them but some of the examples are not simple enough for me to understand, some of them are simple but they include only complicated codes which I cannot follow. By the way, it kinda looked like I directed my question to only you, but if the other respondents would like to add something I'd love to hear. @RobPratt $\endgroup$ – madetolast Apr 24 at 17:45
  • 1
    $\begingroup$ For model formulation (not algorithms or heuristics) I can recommend the book "Model Building in Mathematical Programming" by H. Paul Williams. $\endgroup$ – prubin Apr 24 at 18:00
  • 1
    $\begingroup$ The problems from the Williams book are all described, modeled, and solved here: go.documentation.sas.com/doc/en/pgmsascdc/9.4_3.5/ormpex/… $\endgroup$ – RobPratt Apr 24 at 18:28

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.