5
$\begingroup$

I am confused by Wikipedia's Linear Programming formulation of the Traveling Salesman Problem, in say the objective function.

Question: If there are n cities indexed 1,...,n, what is city with index 0?

This can be seen in the objective function which has the summation of $c_{ij} x_{ij}$ from i=0...n. Also seen in the third and forth constraint.

enter image description here


It seems like Wikipedia's ILP formulation of the TSP is wrong/incomplete. What changes are needed to make it correct?

There is also an older/different version of the formulation, is this correct?

enter image description here

And another one found on Stackexchange

enter image description here

$\endgroup$
  • $\begingroup$ interesting read: en.wikipedia.org/wiki/… People seem to be aware that the formulation is wrong and why it's wrong, but have not fixed it yet. $\endgroup$ – LinAlg Oct 6 '16 at 22:44
  • $\begingroup$ @LinAlg Thanks for pointing that out with the wiki talk page. With my extremely limited knowledge in TSP and ILP, I cannot figure out the correct formulations. Do you mind writing an answer with the correct range for i and j? $\endgroup$ – Nyxynyx Oct 6 '16 at 23:04
  • $\begingroup$ A long time ago I published a paper about the $\texttt{Traveling Salesman Problem}$: New Monitoring Parameter for the Traveling Salesman Problem. F. P. Marin, Phys. Rev. Letters, $\mathbf{77}$, N$^{\circ}$ 26, pag. 5149-52, 1996. $\endgroup$ – Felix Marin Oct 6 '16 at 23:07
  • $\begingroup$ @LinAlg Duoduoduo suggested changing the appearance of 0 to 1, while based on Lesser Cartographies discussion, I need t to be 1 because I am interested in the traditional Traveling Salesman Problem where he visits every other city only once. Is the fix for the current formulations to add the sixth constraints involving the t variable and set t to 1? $\endgroup$ – Nyxynyx Oct 6 '16 at 23:10
  • $\begingroup$ That is indeed one way to fix this formulation. However, I'm not sure if this is the most efficient formulation. A quick Google search on "mixed integer tsp subtour" shows more commonly used (or taught) formulations. $\endgroup$ – LinAlg Oct 7 '16 at 0:36
-3
$\begingroup$

Example: Lp Formulation of TSP

Consider the following distance-matrix of 4-Cities TSP:

    To

From 1 2 3 4

1

13 21 26 2 10

29 20 3 30 20 5 4 12 30 7

Exclude the the Diagonal Variables (X11, X22, X33, X44) from the Distance Table as shown above

The following table represents the Assignment Model + the Additional Constraints resulting from ui – uj + n xij <= n-1; i,j = 2, . ., n & i ≠ j

n = 4 ui – uj + n xij <= 3; i,j = 2, . ., n & i ≠ j

n xij + ui – uj <= 3

4 X23 + U2 – U3 ≤ 3 (i = 2, j = 3) 4 X24 + U2 – U4 ≤ 3 (i = 2, j = 4) 4 X32 + U3 – U2 ≤ 3 (i = 3, j = 2) 4 X34 + U3 – U4 ≤ 3 (i = 3, j = 4) 4 X42 + U4 – U2 ≤ 3 (i = 4, j = 2) 4 X43 + U4 – U3 ≤ (i = 4, j = 3)

V’s X12 X13 X14 X21 X23 X24 X31 X32 X34 X41 X42 X43 U2 U3 U4
OF 13 21 26 10 29 20 30 20 5 12 30 7

1 1 1 1 = 1 2 1 1 1 = 1 3 1 1 1 = 1 4 1 1 1 = 1 5 1 1 1 = 1 6 1 1 = 1 7 1 1 1 = 1 8 1 1 1 = 1 9 4 1 -1 ≤ 3 10 4 1 -1 ≤ 3 11 1 -1 1 ≤ 3 12 1 1 -1 ≤ 3 13 4 -1 1 ≤ 3 14 1 -1 1 ≤ 3

The associated LP consists of the Assignment Model + the Additional Constraints.

Minimize 13X12 + 21X13 + 26X14 + 10X21 + 29X23 + 20X24 + 30X31 + 20X32 + 5X34 + 12X41 + 30X42 + 7X43 s.to: C1 1X12 + 1X13 + 1X14 = 1 C2 1X21 + 1X23 + 1X24 = 1 C3 1X31 + 1X32 + 1X34 = 1 C4 1X41 + 1X42 + 1X43 = 1

C5 1X21 + 1X31 + 1X41 = 1 C6 1X12 + 1X32 + 1X42 = 1 C7 1X13 + 1X23 + 1X43 = 1 C8 1X14 + 1X24 + 1X34 = 1

C9 4X23 + 1U2 - 1U3 <= 3 C10 4X24 + 1U2 - 1U4 <= 3 C11 4X32 - 1U2 + 1U3 <= 3 C12 4X34 + 1U3 - 1U4 <= 3 C13 4X42 - 1U2 + 1U4 <= 3 C14 4X43 - 1U3 + 1U4 <= 3 Integer: U2, U3, U4 Binary: All Xs

Solution Summary for LP of TSP:

Decision Solution Unit Cost or
Variable Value Profit C(j) 1 X12 1.0000 13.0000 2 X13 0 21.0000 3 X14 0 26.0000 4 X21 0 10.0000 5 X23 1.0000 29.0000 6 X24 0 20.0000 7 X31 0 30.0000 8 X32 0 20.0000 9 X34 1.0000 5.0000
10 X41 1.0000 12.0000 11 X42 0 30.0000 12 X43 0 7.0000
13 U2 0 0
14 U3 1.0000 0
15 U4 2.0000 0

Objective Function (Min.) =  59.0000    

The Route is: X12 – X23 – X34 – X41 = 59

$\endgroup$
  • 2
    $\begingroup$ Could you please format your answer? $\endgroup$ – Glorfindel Apr 16 '17 at 16:16
  • $\begingroup$ Format will help tremendously, thank you! $\endgroup$ – Nyxynyx Apr 21 '17 at 17:24

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.