Talk:Travelling salesman problem/Archive 2

Archive 1

Archive 2

ILP formulation always infeasible?

Maybe I am missing something. In the ILP formulation, I don't believe the last set of constraints can ever be feasible. The constraints I suspect are invalid are the following, which are supposed to ensure a single tour.

${\begin{aligned}&u_{i}-u_{j}+nx_{ij}\leq n-1&1\leq i\neq j\leq n\end{aligned}}$

Consider the trivial case of two cities. The only solution in this case (excluding these constraints) is $x_{1,2}=1$ and $x_{2,1}=1$ (i.e. the salesman must travel from city 1 to 2 and then back from city 2 to 1). The suspect constraints can be simplified as follows (sorry for the excruciating detail):

${\begin{aligned}u_{1}-u_{2}+nx_{1,2}&\leq n-1\\u_{1}-u_{2}+2\times 1&\leq 2-1\\u_{1}-u_{2}+2&\leq 1\\u_{1}-u_{2}&\leq 1-2\\u_{1}-u_{2}&\leq -1\\\end{aligned}}$

${\begin{aligned}u_{2}-u_{1}+nx_{2,1}&\leq n-1\\u_{2}-u_{1}+2\times 1&\leq 2-1\\u_{2}-u_{1}+2&\leq 1\\u_{2}-u_{1}&\leq 1-2\\u_{2}-u_{1}&\leq -1\\u_{1}-u_{2}&\geq +1\\\end{aligned}}$

In other words, $u_{1}-u_{2}$ must be less than $-1$ and greater than $+1$, which is a contradiction. For what its worth, I believe this issue extrapolates to more cities too (but its not as obviously incorrect). Did I make a mistake? — Preceding unsigned comment added by 151.190.254.108 (talk) 21:49, 29 August 2013 (UTC)

This is a very interesting observation, but I'm skeptical that it creates a problem for the case of more than 2 cities. You've shown that, for all n, $x_{ij}$ and $x_{ji}$ are prevented from both equalling 1; with more than two cities it is in fact necessary to prevent this, because allowing it would allow solutions with some two-city mini-tours. Duoduoduo (talk) 12:24, 30 August 2013 (UTC)

It appears to me that one of the cities is supposed to be indexed as 0, in which case the problem of false infeasibility does not arise because the constraints with u_i etc. in them don't involve u₀: they are given as applying to $1\leq i\neq j\leq n$. For example, in the two-city case with cities 0 and 1, the constraints disappear entirely. Duoduoduo (talk) 18:20, 30 August 2013 (UTC)

I suspect this might be correct, but I'm not sure: certainly when a constraint is removed from this set, the problem becomes feasible, but I'm not sure if the single tour requirement is maintained (it might be). With regards to whether or not the infeasibility extends to more than two cities, I'll include the simplification for three cities. There are two possible solutions with three cities: city 1 to 2 to 3 and city 1 to 3 to 2 (all other solutions can be formed by rotating those two). I'll use the first solution in this example.

City 1 to 2 to 3 corresponds to $x_{1,2}=x_{2,3}=x_{3,1}=1$, $x_{2,1}=x_{3,2}=x_{1,3}=0$, and $n=3$. We can simplify the suspect constraints as follows:

${\begin{aligned}u_{1}-u_{2}+nx_{1,2}&\leq n-1\\u_{1}-u_{2}+3\times 1&\leq 3-1\\u_{1}-u_{2}+3&\leq 2\\u_{1}-u_{2}&\leq 2-3\\u_{1}-u_{2}&\leq -1\\u_{2}-u_{1}&\geq 1\\\end{aligned}}$	${\begin{aligned}u_{2}-u_{1}+nx_{2,1}&\leq n-1\\u_{2}-u_{1}+3\times 0&\leq 3-1\\u_{2}-u_{1}&\leq 2\\\end{aligned}}$
${\begin{aligned}u_{2}-u_{3}+nx_{2,3}&\leq n-1\\u_{2}-u_{3}+3\times 1&\leq 3-1\\u_{2}-u_{3}+3&\leq 2\\u_{2}-u_{3}&\leq 2-3\\u_{2}-u_{3}&\leq -1\\u_{3}-u_{2}&\geq 1\\\end{aligned}}$	${\begin{aligned}u_{3}-u_{2}+nx_{3,2}&\leq n-1\\u_{3}-u_{2}+3\times 0&\leq 3-1\\u_{3}-u_{2}&\leq 2\\\end{aligned}}$
${\begin{aligned}u_{3}-u_{1}+nx_{3,1}&\leq n-1\\u_{3}-u_{1}+3\times 1&\leq 3-1\\u_{3}-u_{1}+3&\leq 2\\u_{3}-u_{1}&\leq 2-3\\u_{3}-u_{1}&\leq -1\\u_{1}-u_{3}&\geq 1\\\end{aligned}}$	${\begin{aligned}u_{1}-u_{3}+nx_{1,3}&\leq n-1\\u_{1}-u_{3}+3\times 0&\leq 3-1\\u_{1}-u_{3}&\leq 2\\\end{aligned}}$

I'm not sure what the best way is to find a feasible solution for six inequalities, but since I had an implementation available I used the Simplex Algorithm. These inequalities can be represented with the tableau (for which the objective function should be minimized and is the result of pricing out unshown artificial variables - i.e. Phase I):

Z	u1	u2	u3	s1	s2	s3	s4	s5	s6	b
1	0	0	0	-1	1	-1	1	-1	1	9
0	-1	1	0	-1	0	0	0	0	0	1
0	-1	1	0	0	1	0	0	0	0	2
0	0	-1	1	0	0	-1	0	0	0	1
0	0	-1	1	0	0	0	1	0	0	2
0	1	0	-1	0	0	0	0	-1	0	1
0	1	0	-1	0	0	0	0	0	1	2

This tableau can be solved in three pivots (on s₂, s₄, and s₆), with a resulting z_b of 3, indicating there is no feasible solution. See what I meant when I said more than two cities wasn't as obviously incorrect?  :-) 151.190.254.108 (talk) 17:08, 3 September 2013 (UTC)

I guess for an intuitive feel, you can take the left three constraints above or the right three constraints above and see the infeasibility. For example, we know $u_{1}-u_{3}\geq 1$, or $u_{1}\geq u_{3}+1$. Subtracting one from the RHS only weakens the constraint, so we know $u_{1}>u_{3}$. Following this pattern on all three constraints from the left above, we get $u_{1}>u_{3}$, $u_{2}>u_{1}$, and $u_{3}>u_{2}$. Obviously, all three of these constraints cannot be true. 151.190.254.108 (talk) 17:19, 3 September 2013 (UTC)

I'm trying to get hold of the book that this section of the article references. Hopefully that will clear everything up. Duoduoduo (talk) 19:22, 3 September 2013 (UTC)

I transcribed the relevant section from Dantzig 1963 here. The third formulation looks to be what we want. Dantzig cites this formulation to an IBM technical report: Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project, Princeton University. Let me know if something appears nonsensical; I expect I made a few transcription errors. Lesser Cartographies (talk) 01:21, 4 September 2013 (UTC)

Thanks very much, Lesser Cartographies! This is very helpful. I'll try to incorporate it into our text. Duoduoduo (talk) 14:12, 4 September 2013 (UTC)

Lesser Cartographies, could you please double-check this in your transcription: where it says one of the equalities is for j=1, 2, ..., n, should it say j=0, 1, ..., n? And for the other equality where it says it's for i=1, 2, ..., n, should it say i=0, 1, ..., n? Thanks. Duoduoduo (talk) 15:12, 4 September 2013 (UTC)

Glad it was useful. I won't have access to the book for another 8 hours or so, but will check it then. Lesser Cartographies (talk) 16:19, 4 September 2013 (UTC)

Confirmed. In the first equation of the third formulation, (j=1,2,...,n). In the second equation, (i=1,2,...,n). It may be wrong, but I have transcribed it faithfully. Lesser Cartographies (talk) 00:54, 5 September 2013 (UTC)

I'd also like to include the first formulation (and I get the cite later today when I'm back at my office). While it's not nearly as efficient, I find it much easier to understand and it might be more helpful to readers with little experience in optimization. (Having the two side-by-side is also instructive.) Lesser Cartographies (talk) 16:43, 4 September 2013 (UTC)

Thank you from me too, Lesser Cartographies. I guess I am still confused over a couple points though. First, as I think Duoduoduo pointed out above, its unusual that the single entry/single exit constraints don't apply to the 0^th city.

Second, if the range of $i$ and $j$ really is $0\ldots n$, then that means both can take on $n+1$ unique values. Given that $x_{i,j}$ indicates traversal from the i^th city to the j^th city, I think that suggests there are $n+1$ total cities, not $n$ (i.e. the variable $x_{0,n}$ indicates traversal from the 0^th city to the n^th; so for $n=1$, $x_{0,1}$ indicates traversal from the 0^th city to the 1^st). This differs from the definition given for the first formulation you transcribed, and I doubt the single tour constraints expect this (although I don't know for sure). 151.190.254.108 (talk) 16:52, 4 September 2013 (UTC)

Regarding your second point, there are definitely n+1 cities in this formulation. I tried to make that clear in line 2 of the text, saying "for cities 0, ..., n". This contrivance of using n+1 cities but not having a dummy variable u₀ is what makes the single tour constraint work. Duoduoduo (talk) 18:02, 4 September 2013 (UTC)

Should there also be adding-up constraints for i,j =0?

Thanks, Lesser Cartographies, for checking that. It seems clear to me that the equations have to be made to hold for all of j=0, 1, ... and i= 0, 1, .... If not, the constraints permit tours of the form (e.g. for 5 cities with n=4) 0→1→0→2→0→3→0→4→0. Here there are no non-zero x_ij for i, j >0, so the proof that there can be no subtours does not work. In fact, setting all u_i and u_j equal to zero satisfies the constraints.

Presumably this is an oversight or typo in the source. Should we consider imposing the adding-up equalities even for i, j =0? There is certainly no harm in including those, since all they do is prevent more than one entry into and exit from city 0. Duoduoduo (talk) 15:25, 5 September 2013 (UTC)

I'm going to spend some time on this tonight and see if anything different occurs to me. Lesser Cartographies (talk) 03:47, 6 September 2013 (UTC)

So let's start by numbering the equations.

${\begin{array}{lrlr}a)\ &\sum _{i=0}^{n}x_{ij}&=1&(j=1,2,\ldots ,n)\\b)\ &\sum _{j=0}^{n}x_{ij}&=1&(i=1,2,\ldots ,n)\\c)\ &u_{i}-u_{j}+nx_{ij}&\leq n-1&(1\leq i\neq j\leq n)\\d)\ &\sum _{i=0}^{n}\sum _{j=0}^{n}d_{ij}x_{ij}&=z\ ({\rm {{Min})}}&\\\end{array}}$

If I understand you correctly, you're making a claim that neither a) nor b) prevent the tour 0→1→0→2→0→3→0→4→0. I think that statement is correct. However, given this additional condition from the text:

$e)\$Choose $u_{i}=t$ if city $i$ is visited on the $t^{\rm {th}}$ step where $t=1,2,\ldots ,n$.

then $u_{i}$ can never be greater than $n$. This is not to say that I've convinced myself that the formulation as a whole is correct, but I'm pretty sure that your example doesn't disprove it. Given the above, do you agree? Lesser Cartographies (talk) 07:00, 6 September 2013 (UTC) If anyone can show me a reasonable way of numbering equations without horking the alignment, I'd be much obliged. Lesser Cartographies (talk) 07:02, 6 September 2013 (UTC)

It horks the alignment, but I believe this is how they expect you to number equations on Wikipedia. It at least lets you use the {{EquationNote}} syntax elsewhere. 151.190.254.108 (talk) 13:42, 6 September 2013 (UTC)

Oh, one more tip. Alignment alternates between left and right with each & in your {align} block. Using two & in a row (&&) will therefore maintain the same alignment. 151.190.254.108 (talk) 13:46, 6 September 2013 (UTC)

Thank you! \begin{array} did the trick. Lesser Cartographies (talk) 14:54, 6 September 2013 (UTC)

Your condition (e) is not part of the problem specification -- it's just one example of how any valid tour is not ruled out by the constraints. It has nothing to do with invalid tours such as 0→1→0→2→0→3→0→4→0. Duoduoduo (talk) 15:21, 6 September 2013 (UTC)

An attempt to derive the invalid constraints

I attempted to derive the last constraint from scratch. I came up with something, but I skipped some steps, and I didn't prove anything. I thought this could be useful for someone to gain some insight on the problem.

I made the assumption that $u_{i}$ is defined as the index in which city $i$ is visited. This means $\delta _{ij}=u_{j}-u_{i}$ can be defined as the number of steps to travel from city $i$ to city $j$, in the list (i.e. +1 means one step forward in the list, +2 means two steps forward, -1 means one step backward, etc). Also, from this definition, $\delta _{ij}=-\delta _{ji}$.

I'm also assuming $n$ is the number of cities (as one might expect), and that $i\in 1\ldots n$.

If...	One of must be true...		Because...
$x_{ij}=1$	$\delta _{ij}=1$		We have traveled forward one city
	$\delta _{ij}=1-n$		We have traveled from the last city back to the first
$x_{ij}=0$	$\delta _{ij}\geq 2$	$\delta _{ij}\leq n-1$	We have traveled forward more than one city
	$\delta _{ij}\geq 2-n$	$\delta _{ij}\leq -1$	We have traveled backward
	$\delta _{ij}=0$		We have not traveled

(By the way, I suspect the issue with the current formulation resulting in infeasibility is an attempt to handle both $x_{ij}=1$ cases with $\delta _{ij}=1$. This is why dropping one constraint makes the problem feasible: it allows the salesman to travel from the last city back to the first. However, I'm not sure if just dropping a constraint allows for any invalid solutions. Later on I repeat the technique I use here, but making this mistake, and I arrived at the transcribed solution.)

If we define city $j=1$ to be the first one (which we can do since a tour is cyclical, and the first city is arbitrary), we can relax the first two constraints as follows.

If...	One of must be true...		Because...
$x_{ij}=1$	$\delta _{ij}=1$	$j>1$	We have traveled forward one city
	$\delta _{ij}=1-n$	$j=1$	We have traveled from the last city back to the first
$x_{ij}=0$	$\delta _{ij}\geq 2$	$\delta _{ij}\leq n-1$	We have traveled forward more than one city
	$\delta _{ij}\geq 2-n$	$\delta _{ij}\leq -1$	We have traveled backward
	$\delta _{ij}=0$		We have not traveled

Next, I relaxed the $x_{ij}=0$ case to just include the whole range.

If...	One of must be true...		Because...
$x_{ij}=1$	$\delta _{ij}=1$	$j>1$	We have traveled forward one city
	$\delta _{ij}=1-n$	$j=1$	We have traveled from the last city back to the first
$x_{ij}=0$	$\delta _{ij}\geq 2-n$	$\delta _{ij}\leq n-1$	We have not traveled from the last city back to the first

Now I attempted to linearly combine the value of $x_{ij}=1$ constraints with those in $x_{ij}=0$ using the value of $x_{ij}$...

		$x_{ij}=1$
		$\delta _{ij}=1\quad \forall j>1$	$\delta _{ij}=1-n\quad \forall j=1$
$x_{ij}=0$	$\delta _{ij}\geq 2-n$	${\begin{aligned}\delta _{ij}\geq 2-n+{\begin{pmatrix}1-{\begin{pmatrix}2-n\end{pmatrix}}\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ij}\geq 2-n+{\begin{pmatrix}1-2+n\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ij}\geq 2-n+{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\quad &\forall j>1\\-\delta _{ij}\leq -2+n-{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ji}+{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\leq n-2\quad &\forall j>1\end{aligned}}$	${\begin{aligned}\delta _{ij}\geq 2-n+{\begin{pmatrix}1-n-{\begin{pmatrix}2-n\end{pmatrix}}\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\geq 2-n+{\begin{pmatrix}1-n-2+n\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\geq 2-n+{\begin{pmatrix}-1\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\geq 2-n-x_{ij}\quad &\forall j=1\\-\delta _{ij}\leq -2+n+x_{ij}\quad &\forall j=1\\\delta _{ji}-x_{ij}\leq n-2\quad &\forall j=1\end{aligned}}$
	$\delta _{ij}\leq n-1$	${\begin{aligned}\delta _{ij}\leq n-1+{\begin{pmatrix}1-{\begin{pmatrix}n-1\end{pmatrix}}\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ij}\leq n-1+{\begin{pmatrix}1-n+1\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ij}\leq n-1+{\begin{pmatrix}2-n\end{pmatrix}}x_{ij}\quad &\forall j>1\\\delta _{ij}-{\begin{pmatrix}2-n\end{pmatrix}}x_{ij}\leq n-1\quad &\forall j>1\\\delta _{ij}+{\begin{pmatrix}n-2\end{pmatrix}}x_{ij}\leq n-1\quad &\forall j>1\end{aligned}}$	${\begin{aligned}\delta _{ij}\leq n-1+{\begin{pmatrix}1-n-{\begin{pmatrix}n-1\end{pmatrix}}\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\leq n-1+{\begin{pmatrix}1-n-n+1\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\leq n-1+{\begin{pmatrix}2-2n\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}\leq n-1+2{\begin{pmatrix}1-n\end{pmatrix}}x_{ij}\quad &\forall j=1\\\delta _{ij}-2{\begin{pmatrix}1-n\end{pmatrix}}x_{ij}\leq n-1\quad &\forall j=1\\\delta _{ij}+2{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\leq n-1\quad &\forall j=1\end{aligned}}$

Substituting $u_{j}-u_{i}$ for $\delta _{ij}$, I now have four constraints.

${\begin{aligned}u_{i}-u_{j}+{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\leq n-2\quad \forall j>1\\u_{i}-u_{j}-x_{ij}\leq n-2\quad \forall j=1\\u_{j}-u_{i}+{\begin{pmatrix}n-2\end{pmatrix}}x_{ij}\leq n-1\quad \forall j>1\\u_{j}-u_{i}+2{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\leq n-1\quad \forall j=1\end{aligned}}$

Or after some finagling:

${\begin{aligned}u_{i}-u_{j}-x_{ij}+{\begin{pmatrix}nx_{ij}{\text{ when }}j>1\end{pmatrix}}&\leq n-2\\u_{j}-u_{i}+{\begin{pmatrix}n-2\end{pmatrix}}x_{ij}+{\begin{pmatrix}nx_{ij}{\text{ when }}j=1\end{pmatrix}}&\leq n-1\end{aligned}}$

I suspect that only one of these constraints is needed, but I don't know how to prove it yet. I demonstrated this to myself by exhaustively trying every combination of parameters that meet the single entry/single exit constraints for $2\leq n\leq 4$.

Nevertheless, using the first constraint (arbitrarily), this makes the ILP:

${\text{minimize}}$	$\sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}\,$ (1)
${\text{subject to}}$	$\sum _{i=1}^{n}x_{ij}=1\quad \forall j\in 1\ldots n\,$ (2)
	$\sum _{j=1}^{n}x_{ij}=1\quad \forall i\in 1\ldots n\,$ (3)
	$u_{i}-u_{1}-x_{i1}\leq n-2\quad \forall i\in 1\ldots n\,$ (4)
	$u_{i}-u_{j}+{\begin{pmatrix}n-1\end{pmatrix}}x_{ij}\leq n-2\quad {\begin{matrix}\forall i\in 1\ldots n\\\forall j\in 2\ldots n\end{matrix}}\,$ (5)
${\text{and}}$	$0\leq x_{ij}\leq 1\quad x_{ij}\in \mathbb {Z} \,$ (6)
	$u_{i}\geq 0\,$ (7)

To confirm my suspicion above that the original formulation considered the route back from the last city to the first infeasible, we can simplify the tables above as shown below.

If...	One of must be true...	Because...
$x_{ij}=1$	$\delta _{ij}=1$	We have traveled forward one city
$x_{ij}=0$	$\delta _{ij}\geq 1-n$	We have not traveled forward one city

(Its worth noting that we ignored the $\delta _{ij}\leq n-1$ case, since apparently the original author did this too. This makes me feel more confident about dropping one of the constraints above.)

Now we linearly combine the constraints again, just like last time...

		$x_{ij}=1$
		$\delta _{ij}=1$
$x_{ij}=0$	$\delta _{ij}\geq 1-n$	${\begin{matrix}\delta _{ij}\geq 1-n+{\begin{pmatrix}1-{\begin{pmatrix}1-n\end{pmatrix}}\end{pmatrix}}x_{ij}\\\delta _{ij}\geq 1-n+{\begin{pmatrix}1-1+n\end{pmatrix}}x_{ij}\\\delta _{ij}\geq 1-n+{\begin{pmatrix}n\end{pmatrix}}x_{ij}\\\delta _{ij}\geq 1-n+nx_{ij}\\-\delta _{ij}\leq -1+n-nx_{ij}\\\delta _{ji}+nx_{ij}\leq n-1\\\end{matrix}}$

Substituting $u_{j}-u_{i}$ for $\delta _{ij}$, again just like last time...

$u_{i}-u_{j}+nx_{ij}\leq n-1$

...which is exactly the transcribed constraint, strongly suggesting that my suspicion was correct. 151.190.254.108 (talk) 21:34, 6 September 2013 (UTC)

Another idea

I just had another idea to try and formulate the transcribed ILP. What if we split the first city between index zero and index n, so that you can go from zero to one, and n-1 to n? This could explain some of the mismatches in bounds we've seen too? In other words: what if city 0 and city n are the same city, and you can only travel from city 0 and to city n? I haven't verified it yet, but this will make the ILP something like:

${\text{minimize}}$	$\sum _{i=0}^{n-1}\sum _{j=1}^{n}c_{ij}x_{ij}\,$ (1)
${\text{subject to}}$	$\sum _{i=0}^{n-1}x_{ij}=1\quad \forall j\in 1\ldots n\,$ (2)
	$\sum _{j=1}^{n}x_{ij}=1\quad \forall i\in 0\ldots n-1\,$ (3)
	$u_{i}-u_{j}+nx_{ij}\leq n-1\quad {\begin{aligned}&\forall i\in 0\ldots n-1\\&\forall j\in 1\ldots n\end{aligned}}\,$ (4)
${\text{and}}$	$0\leq x_{ij}\leq 1\quad x_{ij}\in \mathbb {Z} \,$ (5)
	$u_{i}\geq 0\,$ (6)

Now the constraints are formulated the same, except with different bounds. Again, I haven't verified that these constraints are sufficient, but it definitely is worth some additional investigation. 151.190.254.108 (talk) 13:56, 9 September 2013 (UTC)

We have to avoid putting original research into the article. Duoduoduo (talk) 15:09, 9 September 2013 (UTC)

Found the problem (I think)

This appears to be the published version of Tucker's algorithm cited by Dantzig. It's solving a significantly different version of the problem.

Miller, C. E.; Tucker, A. W.; Zemlin, R. A. (Oct. 1960), "Integer Programming Formulation of Traveling Salesman Problems", JACM, 7 (4): 326–329, doi:10.1145/321043.321046 {{citation}}: Check date values in: |date= (help)

From the problem statement:

A salesman is required to visit each of $n$ cities, indexed by $1,\ldots ,n$. He leaves from a "base city" indexed by 0, visits each of the $n$ other cities exactly once, and returns to city 0. During his travels he must return to 0 exactly $t$ times, including his final return (here $t$ may be allowed to vary), and he must visit no more than p cities in one tour. (By a tour we mean a succession of visits to cities without stopping at city 0.) It is required to find such an itinerary which minimizes the total distance traveled by the salesman. (emphasis added)

I need to go through the paper carefully to make sure what Dantzig quoted was indeed this algorithm, but at first glance everything is mostly identical, except for this little nugget:

If $t$ is fixed it is necessary to add the additional relation:

${\begin{array}{rl}\sum _{i=1}^{n}x_{i0}=&t\\\end{array}}$

Given this constraint I believe the formulation is correct for the problem it was designed to solve. Setting $t=1$ may solve the traditional TSP, but at this point I'm not willing to commit yes or no.

Lesser Cartographies (talk) 22:36, 6 September 2013 (UTC)

That looks good: we're doing the case t=1, in which case as you observe, we need to put in the adding up constraint for the number of arrivals at city 0. Then maybe the other "missing" constraint, for the number of departures from city 0, is implied by all the other constraints. That would fit with the puzzling version that was previously here, which had j=0, ..., n but i=1, ..., n. Duoduoduo (talk) 22:50, 6 September 2013 (UTC)

Where next on ILP?

Nice catch—both of you. I'm a little concerned that this is to opaque to have in the article, at least by itself. Dantzig's first formulation is inefficient but reasonably clear. Any thoughts on whether we should add the first formulation and/or remove this one? Lesser Cartographies (talk) 22:57, 6 September 2013 (UTC)

The second of the three formulations looks very impractical -- it says

These conditions are not enough to characterize a tour even though the $x_{ij}$ are restricted to be integers in the interval

${\begin{aligned}0\leq x_{ij}\leq 1\\\end{aligned}}$

since sub-tours like those in Fig. 26-3-IV [omitted] also satisfy the conditions. However, if so-called loop conditions like

${\begin{aligned}x_{12}+x_{23}+x_{31}\leq 2\end{aligned}}$

are imposed as added constraints as required, these will rule out integer solutions which are not admissible.

This is vague about how many of these "as required" there are, but it gives the impression that one of these has to be imposed for every possible invalid subtour, which gives a combinatorially large number of these loop conditions.

I'll take a look at the first one of Dantzig's. Duoduoduo (talk) 16:42, 7 September 2013 (UTC)

I think the first version is not so simple. Just as in the one in our text, for this one we would have to explain how it prevents invalid disjointed subtours. Dantzig says this in that regard: It is not difficult to see that an integer solution to this system is a tour [Flood, 1956-1]. The fact that he didn't actually show it means that it takes a lot of exposition to show it; so our presentation would be just as lengthy as is our current presentation. Further, the one we have in there currently is, I think, the most commonly used version. Duoduoduo (talk) 13:10, 8 September 2013 (UTC)

I think the MTZ formulation of the problem in this article is a less ambiguous version of the formulation that appears on the page — Preceding unsigned comment added by 24.39.134.222 (talk) 16:30, 24 October 2014 (UTC)

References

Conversion from ATSP to TSP

Is the explanation about solving asymmetric TSP by converting it to a symmetric instance of size 2N based on this 1983 paper by Jonker & Volgenant? If so, we may have a problem. In 1986 they published erratum saying

Our previously presented transformation of partly asymmetric into symmetric traveling salesman problems is shown to be incorrect. It only yields a lower bound on the optimal cost.

Eltoder (talk) 02:27, 21 January 2016 (UTC)

First Figure Caption Wrong? =

It talks about a "loop" between vertices, where it should have said simply "route" or "edge", I believe. — Preceding unsigned comment added by 86.30.182.2 (talk) 12:47, 9 May 2017 (UTC)

Salesperson

@David Eppstein: I seem to have botched my previous search somehow. I do find many papers using the term, as far back as the 60s. My bad. (I still think the subtext in the commit message I reverted that using "salesman" is sexist worthy of an eye roll, but that debate is not for here; the criterion is whether the term is actually used, and it is.). — Gamall Wednesday Ida (t · c) 19:58, 1 June 2017 (UTC)

Thanks. Anyway, regardless of whether you believe that continuing to use "salesman" is automatically sexist in itself (I certainly wouldn't attempt to un-gender the title of Death of a Salesman, for instance), the IP editor's edit summary removing this phrase, calling attempts to use non-gendered language as "pointless shit", comes across as extremely sexist. —David Eppstein (talk) 20:08, 1 June 2017 (UTC)

Yes, I saw the IP's summary. Edits with outrageous summaries, especially by IPs, are often reverted on sight, and sometimes the following scenario happens: someone introduces nonsense. An IP reverts it and insults people in its summary instead of explaining. An editor reverts the IP based on the summary. The nonsense stays. Travelling salesperson seems strange to my ears, and I've seen WP:RGW editing on such patterns before, so I checked. (And then I messed up ;) ) — Gamall Wednesday Ida (t · c) 20:37, 1 June 2017 (UTC)

It has the convenient property that "traveling salesperson" can still be abbreviated "TSP". I thought the terminology was fairly recent, but checking Google scholar I see publications from the mid-1970s that already used it. —David Eppstein (talk) 20:48, 1 June 2017 (UTC)

I thought likewise -- would have bet money on that -- but it goes back even a decade before the mid-1970s. Like I said earlier: as far back as the 60s. For instance Narasimhan, Giri, and Michiel Smid. "I Preliminaries." Introduction to the Theory of Analytic Spaces. Springer Berlin Heidelberg, 1966. has a section on "Worst-case analysis of the 2-OPT algorithm for the traveling salesperson problem". — Gamall Wednesday Ida (t · c) 05:33, 2 June 2017 (UTC)

That can't be right — Smid's not old enough. Google scholar is mixing up the Analytic Spaces book by Raghavan Narasimhan with a 2007 book, Geometric Spanner Networks, by Giri Narasimhan and Michiel Smid. But the mid-1970s references are real. —David Eppstein (talk) 06:04, 2 June 2017 (UTC)

Ah ok, that makes more sense. Thanks. — Gamall Wednesday Ida (t · c) 07:30, 2 June 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Travelling salesman problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20071025205411/http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf to http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 12:46, 2 December 2017 (UTC)

Proposed merge with Multi-fragment algorithm

Since this is a subset of the TSP, it should belong there itself, not as a separate page. The only reference to this article's title is a single paper where the word just appears once. Daiyusha (talk) 05:08, 17 November 2018 (UTC)

There are plenty more references to this but I think it might be retitled "multi-fragment heuristic" as there are more hits. Google Scholar gives me my own paper "Fast hierarchical clustering and other applications of dynamic closest pairs" first, but others that are maybe more specific to this method include El Krari et al "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" [1]; Blazinskas and Misevicius "Generating High Quality Candidate Sets by Tour Merging for the Traveling Salesman Problem" [2]; Hashempour and Lombardi "Evaluation of heuristic techniques for test vector ordering" [3]; Rego et al "Traveling salesman problem heuristics: Leading methods, implementations and latest advances" [4] etc. My feeling is that there's enough material on this for a standalone article, but also that expanding the main TSP article to include this and all the other equally-notable heuristics (nearest insertion, farthest insertion, etc) would blow up what is already a long article (72k and 58 footnotes) too much. Better to use Wikipedia:Summary style and split off more subtopics into satellite articles like this one to bring the article down to a more manageable size. —David Eppstein (talk) 07:30, 17 November 2018 (UTC)

Against the merge

The multi-fragment algorithm deserves its own page, as the nearest neighbour algorithm (for the TSP) also deserves. The TSP page is already too cluttered. In fact, all algorithms which are explained there should have their own dedicated page, if they haven't yet. Also, it should not be renamed "multi-fragment heuristic". Multi-fragment is an algorithm. If it's an heuristic or not, we don't care. It's just a category which this algorithm falls into. — Preceding unsigned comment added by Nbro (talk • contribs)

--78.229.106.132 (talk) 10:08, 28 January 2019 (UTC)== Why exactly once? ==

MClerc (talk) 21:21, 4 January 2019 (UTC)In 2.1 it is written: "It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once"

But it is not the original TSP as described at the very beginning. Let us consider the following graph: A<->B=1 A<->C=1 B<->C=5

If the salesman starts from A, wants to visit B and C and coming back to A, the shortest path is A -> B -> C -> A (length 4), and not at all A -> B -> C (length 7). Therefore, for a realistic TSP the "exactly once" condition should be relaxed, which implies that the total number of possibilities is greater than n!.

It's fairly easy to show that if a path visits the same point twice, one can construct a shorter path that only visits once.--agr (talk) 21:28, 4 January 2019 (UTC)

We are speaking here of a tour, not just a path. What about the given example (starting from A and back to A)?

TSPLIB paragraph & links

Although the link generally works (the SSL certificate for the TSPLIB website expired, but they'll probably fix it) everything on the external TSPLIB site doesn't seem to work, not links to the data, links to results and examples, etc. Not sure if this is a case where the paragraph should be changed, removed, or none of those, so figured i'd ask here.

DanielTahar (talk) 02:16, 24 July 2019 (UTC)

Quantum Computing

I wanted to add some information about quantum computers and quantum algorithms being applied to solve tsp. Should I put this under "Computing a Solution" or does it warrant its own section?

Forehann8651 (talk) 16:34, 12 November 2019 (UTC)

Human and animal performance

I found some great research about cognitive psychologists using pigeons to model tsp. Since this seems similar to human performance, should I rename the Human performance section to Human and animal performance and put it under there?

Forehann8651 (talk) 21:56, 20 November 2019 (UTC)

Revising the animations

At some point it would be worthwhile to recreate the animations of the different TSP methods so that the two endpoints are joined. As is, it's not clear that the paths return to their original points, rather than simply visiting every point once. If you assumed the latter, then the optimal solution of distance 249 looks incorrect as you easily see that you could swap the order of the two top right points and get a shorter path.

R0uge (talk) 18:25, 24 July 2019 (UTC)

Agreed—they appear wrong as drawn. 167.131.0.195 (talk) 23:19, 2 January 2020 (UTC)

Political Correctness

Should this be Traveling Salesperson Problem? I seem to remember it being changed

--143.53.132.154 10:56, 25 July 2006 (UTC)

Nonsense (IMHO). In practically all scientific publications dealing with it, it's called Travel(l)ing SalesMAN Problem. It's simply how it's called. Period.

--85.127.5.34 13:35, 29 April 2007 (UTC)

It is usually called TSP, whether that means Travelling Salesman Problem or Travelling Sales Person (and the "problem" is added later as TSP problem) or Travelling Salesperson Problem. Either way, the use of "person" rather than "man" is becoming more widespread.

Sorry for the irrelevant humor, but I wonder if any Star Trek writer ever considered putting a reference to the "Travelling Sales-being Problem" (Or a some joke about a travelling Ferengi) Jimw338 (talk) 01:01, 10 March 2021 (UTC)

Well it could be called Travelling Sales Route Problem. Not sure why there is needed being, man or woman.

How the Peano Curve can lead to an approximate but very fast solution to the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is NP-complete, or at least NP-hard, meaning that it cannot be solved exactly in polynomial time (there is no algorithmic solution having an execution time upper-bounded by n to the m, for problem size n and any positive integer m).

An example of a very fast but approximate solution is the one used by some nonprofit organizations that deliver food to shut-ins: the positions of the vertices (delivery locations) are plotted on a printed approximation to a space-filling curve (SFC) such as a Peano Curve, and the visit order is read out as the distances along the SFC.

One source of error in this approximate solution is the nature of a cartesian SFC approximation, where each plotted (x,y) vertex may be very close to up to four of the SFC points, depending on the relative sizes of the physical TSP and SFC points. This error would yield up to four candidates for the position of each vertex in the solution path. — Preceding unsigned comment added by David spector (talk • contribs) 13:39, 22 September 2016 (UTC)

constraints on u_i needed, or helpful to state?

Isn't it necessary to state constraints on what the artificial variables u_i are? I.e. something like 1 <= u_i <= n, for all i. Or maybe it needs to be 2 <= u_i < n, or 0 <= u_i <= n-1. The Integer Linear Programming Solution section currently reads: ${\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&i,j=1,\dots n\\&x_{ij}{\text{ integer}}&i,j=1,\dots n\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&j=1,\ldots ,n\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&i=1,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&2\leq i\neq j\leq n.\end{aligned}}$

I've seen a statement of the TSP problem in SAS software documentation according to the "MTZ" formulation (for Miller-Tucker-Zemlin 1960), which includes 2 <= u_i < n as a constraint. I guess it is possible that the constraint is not needed, that any solution already requires that constraint to be met. That the MTZ 1960 formulation has been improved upon, i.e. that constraint stated by them is in fact satisfied by other aspects of the problem already.

But, anyhow, it could simply be noted that the u_i are artificial variables that represent a numbering from 1 to n. (And implicitly then 1 <= u_i <= n.) It may a tad redundant to state it, mathematically, but it could possibly help readers a lot to simply be given the interpretation, that the u_i variables will turn out to represent a numbering of the optimal sequence. And that constraining the u_i to be whole numbers in the 1 to n range does not cause any deterioration of the solution, it is a constraint that can be added (though is not necessary). I think that would help up front in stating the problem, that here is what the u_i's are going to be. — Preceding unsigned comment added by 95.105.186.15 (talk • contribs) 11:50, 31 March 2020 (UTC)

Brute force computer illustrations misleading?

There are two animations comparing the brute force to a heuristic solver. However, the illustrations are at best misleading, maybe wrong. The different found optimal paths change the end-point. That does not correspond to the TSP where the start and stop nodes are fixed. — Preceding unsigned comment added by SweRavn (talk • contribs) 14:58, 27 August 2021 (UTC)