Talk:Travelling salesman problem/Archive 1

This is an archive of past discussions about Travelling salesman problem. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

General Case

Shouldn't the ATSP be cast as the general case of the TSP, with the equal-cost-in-both-directions constraint relaxed over some subset of the edges?

I agree. Asymmetric TSP: "The special case where the distance from A to B is not equal to the distance from B to A" is not a special case but a generalized case. I'll remove the word "special". Bo Jacoby 10:20, 6 March 2006 (UTC)

TSP with triangle inequality

"the distance between A and C must be at most the distance from A to B plus the distance from B to C. " (citation needed)

This is easy to understand when we talk about points in some space like Euclidian or a sphere.

But when we talk about graphs, it's confusing because in any graph that contains the path {A,B,C}, the distance between A and C is never greater than the distance between A and B plus the one between B and C. This is true even for graphs that doesn't conform to triangle inequality!!!

I think something like this would be clearer to most readers: "the shortest distance between A and C not passing through B must be at most the distance from A to B plus the distance from B to C. "

what about the word direct? I.E. lenght of the road connecting the two cities. A direct route might not be the easiest/shortest.

But I'm not sure if it's matematically right!

It's not. First, it's not true that in any graph that contains the path {A, B, C}, the distance between A and C is never greater than the distance between A and B plus the one between B and C. For example, take the complete graph on 3 vertices with edge weights 3, 1, and 1. In this case, we have the distance between A and C being 3 and the distance from A to B plus the distance from B to C being 2. Note that the distance between two vertices in the graph is the weight of the edge between them, not the shortest distance in the graph. I hope that clears up your confusion. Cgray4 09:51, 4 April 2006 (UTC)

Princeton proof?

The Princeton link refers to a "proof" of the TSP problem for a specific configuration of cities in Germany. The "proof" relies on a computer program, the associated network of computers, and the computer hardware. It is perfectly possible that there exists a verifiable proof that the computer program is correct but there is a finite, non-zero probability of undetected failure of any one of the hardware components.

Another comparable effort is the verification of Goldbach's conjecture for very large numbers. As Ian Paisley, a prominent Northern Irish politician might have said - "If you believe that you'll believe anything".

Colin M Davidson

How fast are the best known deterministic algorithms?

"Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city and then returns to the starting city?"

Shouldn't it be "... that visits each city once ..."?

Yes. Thanks. Mikkalai 20:37, 16 Nov 2004 (UTC)

a) only yes/no problems are NP etc. The TSP "finding the route" etc. is BPP (prob'y the reference easiest to access is Papadimitriou's 1998 textbook, in the part(s) where he presents the complexity classification for non-yes/no probs.)

you mean FNP not BPP right? it is usually believed dthat BPP = P Nr9 08:14, 8 April 2006 (UTC)

Optimal solution for 15,112 cities

According to this link, [1], an optimal solution has been found for the 15,112 city problem, not just an approximate solution. --Petero2 16:33 Jan 31, 2003 (UTC)

-- The fact remains that this is an NP hard problem, and as such an exact method cannot solve the problem in polytime. This is just one instance of a TSP that has been solved. ---Smremde 11:58, 25 July 2006 (UTC)

a proposed algorithm

How would this incremental algorithm work well (in terms of solution quality):

-start with tree looped cities

-for each new city:

--consider each existing edge

---get its current lenght

---get the total distance from the city being added to the edge's endpoints

---substract these two values

--connect the city through the shortest detour

?

It is quadratic in terms of running time but how good solutions does it produce? It always produces solutions with no crossings. Another possibility might be to run the algorithm a few times with randomized order of the cities. Honnza 10:23, 22 July 2006 (UTC)

This is the greedy algorithm. It performs reasonably well in the Euclidian case (not as well as the advanced approximation schemes), an in fact should be subquadratic in that case. In the general case where the triangle inequality is not valid, this method can be arbitrarily bad. CRGreathouse (t | c) 06:53, 21 September 2006 (UTC)

Question

it is easily seen that in the planar case an optimal tour visits cities only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would decrease the tour length).

Okay, so . . . what if three cities are colinear? In particular, what if we consider a case with the home city and two other cities, and all three are colinear? Do we just figure that the intervening city is a point and can be circumvented with arbitrarily low expenditure of distance, so call it zero? —Simetrical (talk • contribs) 02:07, 20 June 2006 (UTC)

Going directly from A to C isn't considered stopping at B, even if A, B, and C are colinear. If they are colinar then there's no difference between stopping at B and going directly from A to C. This all comes from looking at the problem as an abstract graph rather than a surface with cities. CRGreathouse (t | c) 06:56, 21 September 2006 (UTC)

two questions on higher-dimensional TSPs

Currently, this article doesn't have much discussion on TSPs in more than two dimensions. Would different approaches be required in order to solve TSPs in higher dimensions?

Also, consider this three-point TSP with the following conditions:

d(a,b) = 5
d(a,c) = 7
d(b,c) = 150

As we can see, this (arbitrary) system isn't possible in normal Euclidean spaces unless higher dimensions are involved.

Again, do we need to use different approaches in solving TSPs of this type? --Ixfd64 21:36, 10 November 2006 (UTC)

the triangle inequality is true in any number of dimensions. It is true for any metric space.

subexp time for euclidian TSP ?

Although the problem still remains NP-hard, it is known that there exists a subexponential time algorithm for it.

Where can I find that algorithm ?

As far as I know, a "subexponential" time algorithm means a polynomial time algorithm (e.g., 2^O(sqrt(log N)) is something like O(sqrt N)). Since Euclidean TSP is NP-hard and the corresponding decision problem is NP-complete, wouldn't finding a polynomial time algorithm for Euclidean TSP would prove P=NP? Therefore, I suspect the quoted statement is incorrect. --68.61.203.204 18:47, 26 November 2006 (UTC)

"Human performance"

These works are so naive. If strip away the psychobabble,

the first hypothesis says that people can quickly solve the TSP because they can quickly find a partridge in a pear tree (bad link here. This is a reference to a centuries old puzzle, where you must find various figures among random drawings, e.g. a contour of a bird or a hare created by branches of a bush ).
the second one says that people solve the TSP because they are smart, since the smarter they are, the faster they solve it.

What a waste of taxpayers' and grant money. `'mikka 16:32, 2 January 2007 (UTC)

Polytime solution in progress?

From "Computational Complexity" section:

"Though see this work-in-progress attempt at a proof of polynomial time calculation for the 2-D undirected graph."

It looks as though the page linked to just claims that TSP is in NP, then presents the details of an approximation algorithm. Should this perhaps not belong here? 140.247.40.63 09:16, 4 February 2007 (UTC)

Nearest Neighbour Algorithm cannot find worst possible solution.

I changed the text that said the nearest neighbour algorithm can find the worst possible solution and removed the asociated request for citation.

The worst possible scenario for the NN algorithm is all points strung upon a line, with the shortest distance being at alternating sides from the central point. eg.

E.......C.AB...D........

The nearest neighbour solution A->B->-C->D->E takes 1+3+7+15=26.

An alternate solution A->E->B->C->D is 10+11+3+7 = 31.

There is a worse solution than the worst possible NN solution. Therefore NN cannot result in the worst possible solution.

All that said, maths is not my strongest point, so please point out if there's a flaw in my position. Thanks.

--irrevenant [ talk ] 03:15, 17 March 2007 (UTC)

Probability question

Is it possible to estimate the probability p(n) of finding a tour without loops at random permutation of n towns uniformly distributed over a square?--Kjells 18:40, 25 April 2007 (UTC)

Consider simulating to get an idea. It seems it should probably be exponentially small.Ninjagecko 12:38, 8 May 2007 (UTC)

Plagiarism?

Compare:

Mathematical problems related to the traveling salesman problem were treated in the 1800s by the Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman. A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 1736-1936. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger. The problem was later undertaken by Hassler Whitney and Merrill Flood at Princeton. A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in Alexander Schrijver's 2005 paper "On the history of combinatorial optimization (till 1960)"

with http://www.tsp.gatech.edu/history/index.html

Mathematical problems related to the traveling salesman problem were treated in the 1800s by the Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman. The picture below is a photograph of Hamilton's Icosian Game that requires players to complete tours through the 20 points using only the specified connections. A nice discussion of the early work of Hamilton and Kirkman can be found in the book Graph Theory 1736-1936 by N. L. Biggs, E. K. LLoyd, and R. J. Wilson, Clarendon Press, Oxford, 1976.

The general form of the TSP appears to be have been first studied by mathematicians starting in the 1930s by Karl Menger in Vienna and Harvard. The problem was later promoted by Hassler Whitney and Merrill Flood at Princeton. A detailed treatment of the connection between Menger and Whitney, and the growth of the TSP as a topic of study can be found in Alexander Schrijver's paper ``On the history of combinatorial optimization (till 1960). —The preceding unsigned comment was added by 143.239.1.153 (talk) 19:33, 1 May 2007 (UTC).

Then alert the person at the URL, though it is entirely possibly the author of that page decided to jointly publish that information on Wikipedia. Ninjagecko 12:41, 8 May 2007 (UTC)

Reference to MATLAB

Firstly, why is there a reference to MATLAB? It is irrelevant. Secondly why does it say that MATLAB is "the language of technical computing"? This is nonsense. MATLAB isn't just a language and it is not THE language of technical computing. A lot of number crunching is done with FORTRAN or C for example. —The preceding unsigned comment was added by 62.56.77.207 (talk) 15:15, 11 May 2007 (UTC).

Reference to Marco Dorigo

The style of this reference, with a title bearing a particular person's name, is objectionable and out of line with the rest of the article (and the overall Wikipedia guidelines). Secondly, the contents of this section, if they should be included at all, belong to a previous section, namely on heuristics. Finally and, in my opinion, most importantly, the work is of little substantial value in practice for the TSP, because a computer implementation of the proposed algorithm is vastly inferior to state-of-the-art heuristics (such as the chained Lin Kernighan), both in terms of computational time and quality of solutions. Cngoulimis 11:00, 16 July 2007 (UTC)

I rewrote and moved this section. Dcoetzee 23:02, 7 August 2007 (UTC)

Contested move request

The following request to move a page has been added to Wikipedia:Requested moves as an uncontroversial move, but this has been contested by one or more people. Any discussion on the issue should continue here. If a full request is not lodged within five days of this request being contested, the request will be removed from WP:RM. —Stemonitis 06:27, 11 August 2007 (UTC)

Travelling salesman problem → Traveling salesman problem — spelling ——Disavian (^talk/_contribs) 19:53, 10 August 2007 (UTC)

WP:ENGVAR explicitly forbids this kind of switching between US and Commonwealth spellings. --Stemonitis 06:27, 11 August 2007 (UTC)
Yes, this should clearly stay where it is, unless a compelling reason to do otherwise is raised. Dcoetzee 13:26, 11 August 2007 (UTC)

The article uses a different spelling than its title. I was simply trying to be consistent. If consensus says that we spell it "travelling" then all instances of the word should be spelled that way in the article. —Disavian (^talk/_contribs) 17:34, 11 August 2007 (UTC)

...Which looks like it was done after I submitted my request. Excellent. —Disavian (^talk/_contribs) 17:35, 11 August 2007 (UTC)

Problems with "Example letting the inversion operator find a good solution" section

Upon reading this twice, it seems to me that it doesn't state its algorithm: you can't simply apply the "inversion" operator over and over again to get to the right solution; there has to be some sort of "guiding" or accept/reject step... the author of that section should state the algorithm used to generate those graphs, or else the section is meaningless and probably should be excised. Ninjagecko 23:16, 8 May 2007 (UTC)

In every generation there is random variation (by inversion) and selection of the shortest tours. The guidance is that the limit of acceptance is slowly lowered. There is no original research in this case. I wrote my algorithm in MATLAB in accordance with the algorithm given by Goldberg.--Kjells 07:28, 10 August 2007 (UTC)

Over yesterday and today I have substantially revised this section for readibility. I have a background in engineering mechanics, not computational complexity, and I may have contributed errors. Also, I did my best to find the likliest reference, but I didn't actually check out the book to verify. Please thoroughly scrutinize my work. David Hillshafer 23:10, 24 August 2007 (UTC)

Spelling

The first line coins the term "traveling salesman problem" and has a note saying that the American spelling is "traveling salesman problem." ...Am I missing something? I glanced at the history to see if it looked like any British-American edit wars occurred, but didn't notice anything in my 5 seconds of searching. I suspect this relates to the difference in spelling between the introductory paragraph and the article, where there are one or two "L"'s in "traveling / travelling"? I suggest we standardise the article in some manner. Personally, I'm a one-L person; but I could care less as long as it's consistent. --Thisisbossi 22:42, 7 February 2007 (UTC)

There are two ls in travelling. The verb is "to travel", not "to travele". Paul Silverman 19:41, 8 February 2007 (UTC)

One L as per Merriam-Webster. [2] --Thisisbossi 22:12, 8 February 2007 (UTC)

Miriam Webster is rubbish Oxford spells it properly. Paul Silverman 21:38, 9 February 2007 (UTC)

Thank you for the link, which answered my initial question; but instead of mocking lingual differences it may have been simpler for you to simply say that one spelling is British and another is American. My initial comment is maintained, however: the spelling should remain consistent throughout the article and including the article's name, and/or the link referring to the American spelling should be modified. I will leave it to the more regular editors of this article to decide how best to pursue this. --Thisisbossi 03:43, 12 February 2007 (UTC)

I saw that too and had to switch back and forth between the text and footnote for a while to see if I was missing something. I've clarified the footnote. -SpuriousQ (talk) 01:05, 15 February 2007 (UTC)

I believe that the footnote had disappeared, which IMO is a bad thing - the article is titled using double-L, but the first paragraph (and the subsequent text) describes the notion using single-L... Where can we add back the fact that the british and american spelling differs? I mean, besides letting the reader discover that the references section actually contains both spellings? :-D -- Jokes Free4Me 06:52, 17 June 2007 (UTC)

Looking at the external links, this what the georgia tech page had to say about it... http://www.tsp.gatech.edu/history/travelling.html Looks like the problem's title is a proper noun. Should be one L regardless of the spelling of traveling/travelling. Keep with the problem's original spelling. Psy wombats 14:46, 23 October 2007 (UTC)

Optimization version NP-complete?

Sorry if the answer to this is obvious, but is the optimization version of this problem ("Find a path with minimum cost.") in NP-complete, or just the recognition version? EDIT: come to think of it, that would put the recognition version in NP, right? 77.49.167.219 13:09, 9 November 2007 (UTC)

NP-complete is a decision problem class, and can only contain decision problems (problems with yes/no answers). Optimization problems can be NP-hard, but not NP-complete. Dcoetzee 00:30, 10 November 2007 (UTC)

TSP in popular culture

It's a pity that there is no article The travelling salesman problem in popular culture. It's probably too offtopic for this one: [3]. --Hans Adler (talk) 20:05, 27 March 2008 (UTC)

What about the ants?

Shouldn't there be a reference on this page to the experiments done with ants which have found that random searching combined with weak pheromone trails result in a much quicker solution to the problem than is possible through mathematics. I realise this doesn't solve the mathematical problem but I think there should at least be a link to an article about the ant approach. 81.156.221.243 16:35, 3 February 2007 (UTC)Sabita Banerji

Is there a reference to this? 194.237.142.10 (talk) 13:35, 30 September 2008 (UTC)

Question:"It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem"

Is there any proof or analysis about this? Thanks.Ifcongif (talk) 01:57, 11 November 2008 (UTC)

see Hamiltonian path problem. `'Míkka >t 02:29, 11 November 2008 (UTC)

If we do not require to return to the original city, does it by definition still a TSP?

in other words, if our problem is to find a hamiltonian path with the lowest cost, is it a TSP? thanks.Ifcongif (talk) 23:53, 17 November 2008 (UTC)

Technically, no. It is closely related though, so closely that some authors might decide to not put the cycle requirement in the definition. It's not the Hamiltonian path problem, since that just asks whether a Hamiltonian path exists, rather than for one of lowest cost. Dcoetzee 02:01, 18 November 2008 (UTC)

Thank you very much.Ifcongif (talk) 02:07, 18 November 2008 (UTC)

Software?

I'm interested in studying this problem, but I don't see good links to software that might help visualize and evaluate algorithms. Does such software exist, and could someone more knowledgeable help document it? 70.251.156.117 (talk) 21:30, 29 November 2008 (UTC)

Translation from DE

One of the editors pointed to the German version of this page, which is in much, much better shape. I’ve started translating the parts that I think are clearly better and thus replaced and expanded a sizeable chunk of the present article. I will continue my slow progress through this task, but sooner or later I will approach areas where the two articles disagree in focus. (For example, this, English version, gives a lot of weight to local search heuristics.) If somebody disagrees with the change of focus my brutal overhaul might constitute, by all means stop me. Also, my English suffers when I translate from German, so I’d appreciate a native speaker to put my output into idiomatic English. Thore Husfeldt (talk) 21:25, 19 January 2009 (UTC)

Nearest Neighbor Algorithm

I believe the current text is incorrect: "Unfortunately, it is provably reliable only for special cases of the TSP, namely those where the triangle inequality is satisfied."

In fact, even for the TSP satisfying the triangle inequality, the approximation can be arbitrarily bad: "Theorem: For every r>1, there exists an instance of the TSP, obeying the triangle inequality, for which the solution obtained by the nearest-neighbor algorithm is at least r times the optimal value." Gross, Jonathan; Yellen, Jay. 1999. Graph Theory and Its Applications. New York: CRC Press. 228-232. So the text ought to be changed, no? Padde 22:51, 18 November 2006 (UTC)

Lingwanjae say: Some people like to create special case to emphasize NN might lead to worst result, and strangely they do not emphasize NN is a good and quick approximation in general case.

For N cities randomly distributed on land, NN algorithm lead to a tour length about 1.25 * exact_shortest_length, which is good for reallife application. Besides, a little modified NN algorithm will yield tour never too long. That is, let salesman always visit the second nearest city. In general case this yield a longer tour then NN but it never lead to the worst tour. Another idea is let salesman always visit the nearest or second nearest city as 1/2 choice. Is there any example of city distribution makes this method walking on the worst tour ? I don't see. —Preceding unsigned comment added by Lingwanjae (talk • contribs) 17:47, 5 March 2009 (UTC)

Political Correctness

I agree and accordingly corrected the notes. —The preceding unsigned comment was added by 89.243.66.153 (talk) 16:20, 4 March 2007 (UTC).

Can we change the traveling salesMAN problem to the traveling salesPERSON problem? —Preceding unsigned comment added by 192.52.218.45 (talk) 00:14, 4 June 2009 (UTC)

Clarification for complexity analysis?

Although calculation of the best route requires exponential time - O(2^n), is it possible to check if a given route is the shortest (or longest for that matter) in polynomial or shorter time, or must you check all of the 2^n routes to see which is the shortest? Perhaps this could be mentioned in the article.

The other thing is that according to the article, the lowest known complexity for solving perfectly is O(2^n), but then it goes on to say that around 30,000 cities have been solved with proof that it's the shortest route. But then doesn't this undermine the O(2^n) complexity, since 2^30,000 is a very large number, much larger than any PC could hope to achieve at present. I'm guessing it's because certain difficult maps may need to check O(2^n) routes, whilst simpler maps (still with the same number of points) may be easier to prove (perhaps more like polynomial time even?). But in any case, it would be nice if this was clarified in the article. —Preceding unsigned comment added by Skytopia (talk • contribs) 01:10, 10 July 2009 (UTC)

For your first question, no, no, and no. It's still NP-hard to test whether there exists a shorter route than one you've already found, the number of routes that could possibly exist is n!, far larger than the 2^n number in your question, and there exist algorithms which (while still exponential) are far faster than testing all possible routes. As for your "other thing", there are two reasons for the difference you observe. First, the complexity of practical implementations, while still exponential, is a far smaller exponential than the best complexity that we can prove mathematically. And second, there's no reason to believe that these 30,000 city instances that have been solved are the hardest possible problems with that size, while the 2^n bound uses worst case analysis. —David Eppstein (talk) 01:59, 10 July 2009 (UTC)

Thanks for clearing that up. Assuming hardest possible problems of a size, I would like to see mention of an approximate of the far smaller exponential for the exact algorithm section. What do you think? One might expect 1.1^n or even 1.01^n (rather than 2^n), even considering that the problems aren't the hardest possible for their size.

(All of the this is talking in terms of an exact solution of course - I assume when you said "is a far smaller exponential than the best complexity that we can prove mathematically", that you mean proving the exponential, rather than speaking in terms of solving the best route only approximately).--Skytopia (talk) 20:51, 10 July 2009 (UTC)

The article includes the claim that even 1.9999^n (for general graphs) is an open problem. Both David Eppstein and me are active researchers in this field and have published algorithms with smaller running times for restricted graph classes, in particular, bounded-degree graphs. (Though nothing as impressive as the bounds you solicit.) There is a certain sensitivity involved in adding "one's own research" to Wikipedia, for reasons of neutrality and undue weight, which is why we may have been reluctant to add these things. But given your questions, maybe a short summary of these results is warranted. Thore Husfeldt (talk) 08:46, 11 July 2009 (UTC)

Yeah go for it. In my opinion it will only do more good than harm. In any case, it can always be replaced or edited at a later time if appropriate. By the way, the reason I thought perhaps even 1.01^n would be reasonable is that for 10s of thousands of cities (which have apparently been exactly solved), 1.01^n explodes quickly. From what I understand now, I can only assume that the example problems given are no where near as hard as they could be, despite having 10,000s of cities.--Skytopia (talk) 01:10, 12 July 2009 (UTC)

Example: Symmetric TSP with four cities

I'm a bit confused as to why this example graph is included in the article if no mention of it is made anywhere in the article. At the very least the image description should include the solution for that particular graph. As I see it the solution would be A-B-C-D. As I don't want to mess with the structure of the article I'll refrain from editing this in, but I believe this should be rectified. Vadigor (talk) 10:17, 22 November 2009 (UTC)

spam link

under further reading, the third entry's hyperlink "Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem" has the target tiny123.com, which is marked by World of Trust as a spam site 132.161.224.94 (talk) 05:21, 30 January 2010 (UTC)

I think this falls more under WP:EL#Redirection sites than spam, but in any case it's not appropriate to use links like that. I replaced it with a citeseer link. Thanks for catching this. —David Eppstein (talk) 07:31, 30 January 2010 (UTC)

Lukas Roots's solution

Don't have any insight but this article claims a 16 year old 'solved' the problem... [4] --67.187.48.82 04:18, 27 April 2006 (UTC)

By referring to the problem as an unsolved problem, and then claiming then he solved it, does he mean to say that he devised an efficient algorithm for an optimal solution or an approximate solution? I did a web search but could not find any reference to this or the algorithm itself online. Whatever he was trying to say, one should be wary of such claims without proper public disclosure. --Amit 00:48, 23 July 2006 (UTC)

--I was misquoted by the local newspaper. My algorithm was a poly-time approximate algorithm. It solved (gave optimal) solutions to specific randomly generated TSPs, but it is still an approximate algorithm. —Preceding unsigned comment added by 140.247.43.99 (talk) 00:52, 3 September 2010 (UTC)

Linear Programing anyone?

This problem can be solved easily by using linear programing. —Preceding unsigned comment added by 210.4.96.72 (talk) 23:46, 5 October 2010 (UTC)

Congratulations! Your discovery will win you a Millennium Prize. Please consider donating some of the prize money to the Wikimedia Foundation. --Lambiam 01:02, 9 March 2011 (UTC)

New Route For Tour of 15 German Cities

Dear Colleagues, I would suggest two things: 1) it was stated that no city was to be visited twice, therefore a closed loop would not be possible without the starting city being visited a second time at the close of the loop; 2)consider the route from Essen to Duisburg to Dusseldorf to Koln to Bonn to Frankfurt to Stuttgart to Munich (bypass Nurnberg and Leipzig for now) to Dresden to Berlin to Hamburg to Bremen to Hannover to Leipzig to Nurnberg. There may be better routes yet, after my first point is taken into consideration. —Preceding unsigned comment added by South Texas Waterboy (talk • contribs) 05:31, 10 July 2010 (UTC)

ad 1) That is rather a wording problem because no city should be _entered_ or _left_ twice. Logically, a salesman has a home and a family and needs to return there. If he lives in Berlin and travels through Germany, he will leave Berlin once and he will enter Berlin once, so this arrival and departure must be counted as one visit.

ad 2) You may try to prove that there are better routes. This route was calculated with a heuristic method, so it needs to be considered as best route UNTIL you can PROVE that there is a better route.

-- Kapitän Nemo from DE (talk) 17:27, 15 March 2011 (UTC)

The map of Germany shows too many cities

The map on top of the article shows more cities than the TSP path links. I find it disturbing as an illustration of TSP: the goal of TSP is to find a path linking all cities of a given set; this image may give the impression that the goal is to find a path between some subset of the given set. I think the map should either show only the 15 main cities of Germany, or show more and show an optimal path between all cities it shows. (The first option is probably easier to achieve.)

(Remark first made on the talk page of the image, copied here for better visibility).

--FvdP (talk) 10:03, 13 April 2010 (UTC)

Moreover, there are only 14 cities on the tour shown; Dortmund, Germany's 8th largest city, is missing. This is ridiculous. --Lambiam 00:59, 12 March 2011 (UTC)

I agree, should be corrected! --Fioravante Patrone (talk) 08:53, 14 March 2011 (UTC)

I asked for a correction in the page of the image. In the meantime, I deleted the picture. Thanks to that picture I lost a lot of time trying to understand what was wrong with me... --Fioravante Patrone (talk) 10:17, 14 March 2011 (UTC)

This was already discussed on German Wikipedia. However, Düsseldorf, Duisburg, Essen and Dortmund are so close together that it is very difficult to fill in an additional city into this map. This map was intended to give a first impression about the problem, so I simply reused the CIA map and added a heuristic route there. For six years, nobody has drawn a better map so far. --Kapitän Nemo from DE (talk) 17:39, 15 March 2011 (UTC)

I was not able to find any trace of a previous discussion in the German wiki. Anyway, I did make a small effort: [5]. I see, however, that it is not guaranteed, contrary to what was written in the caption of the figure, that the depicted one is an optimal route. So, there is not too much point in trying to "improve" this, if it were to be used in the opening of the article. --Fioravante Patrone (talk) 02:55, 20 March 2011 (UTC)

Thanks for doing something about this. A long time ago I constructed the image the below to replace the misleading 15 German cities map. It shows the tsp route from the 1832 book for travelling salesmen, based from the survey of Shrijver (2005). I don’t know why I abandoned the project – I was probably frustrated by the behaviour of the tour around Hanau. One could solve that by lying about where Hanau is (i.e., moving it slightly South). Also, I guess the plan was to underlay a topographical map of Germany. Anyway, if somebody wants to do something with the SVG, go ahead. Thore Husfeldt (talk) 11:53, 14 March 2011 (UTC)

Hamiltonian Cycle?

In the graph-theoretic formulation of the problem, the TSP problem is said to be equivalent to finding a Hamiltonian cycle in an undirected, weighted graph. As I understand it, however, the solution to the TSP problem is not a cycle. Do solutions to the TSP problem really arise from Hamiltonian cycles? The most obvious way of obtaining such a solution form a hamiltonian cycle is to eliminate the largest weight edge from the cycle, but it is not obvious to me that this is optimal in the TSP sense. —Preceding unsigned comment added by 108.114.86.19 (talk) 22:48, 11 April 2011 (UTC)

It's "equivalent" in the sense that both are NP-complete problems and the definition of NP-completeness implies an equivalence. But I suspect what you really mean is that the Hamiltonian cycle problem is a special case of the TSP problem. Specifically, an

n

-vertex graph

G

has a Hamiltonian cycle if and only if the complete graph

K n

, with edge lengths equal to one for edges in

G

and two otherwise, has a traveling salesman tour of length at most

n

. I guess the description in the present article has it kind of muddled; it could use improvement. —David Eppstein (talk) 23:05, 11 April 2011 (UTC)

Conversion to symmetric TSP: OR?

The section Solving by conversion to symmetric TSP presents a method for transforming any instance of the general TSP to a symmetric problem. I don't understand how this works; specifically, there should be a method of extracting a solution of the original problem from a solution of the transformed problem. So assume there are four cities A, B, C, and D, and that we have this tour as the solution to the transformed (eight-city) problem: A · B' · C · A' · D · C' · B · D' · A. How do we obtain from that a tour visiting each of A, B, C, and D just once before returning to A, in such a way that we can see that optimality is preserved? This is not explained. The section is totally unreferenced, and I suspect that this is original research. --Lambiam 19:34, 17 May 2011 (UTC)

It hasn't been explained well in the article. An arc connected to A means "this arc leaves A", and an arc connected to A' means "this arc enters A" (or the other way round, as long as you are consistent). You have to force it so that A and A' are connected, which you can either do by explicitly constraining those arcs to be used or by giving them a negative enough cost. Taking part of your solution: B' · C · A' means "You leave C and go into B" and "You leave C and go into A", which is infeasible. Here's an example in literature http://cran.r-project.org/web/packages/TSP/vignettes/TSP.pdf 122.57.158.46 (talk) 05:51, 3 June 2011 (UTC)

Page should be moved

This page should be called Travelling salesperson problem. I tried to move it, but had trouble because the new page location already exists, and redirects to this page. It should be the other way around. I'm not sure how to get around that, but I'm sure other people do. I'm a university student in computer science, and all my professors say travelling salesperson, not salesman. I think the new name has become accepted enough that the title of this page can become politically correct now. Spock of Vulcan (talk) 21:45, 22 July 2009 (UTC)

It is not our business to lead others to corrected terminology; rather, we should follow what terminology people use most frequently regardless of whether it is politically correct or not. My check of Google hit counts revealed 20x as many pages still calling it travelling salesman compared to the number with the corrected terminology. Please move it back. —David Eppstein (talk) 22:47, 22 July 2009 (UTC)

I agree, the page should be moved back until such time as the new name is actually dominant in popular usage. Wikipedia naming is descriptive, not prescriptive, and some people may not even recognise the topic with its new name. Dcoetzee 00:49, 23 July 2009 (UTC)

I dissent. People may search for "travelling salesman" but be redirecting to "travelling salesperson" without becoming confused. It should go without saying that "correct terminology" is not necessarily the most popular terminology as measured by Google hit counts. Neither Dcoetzee nor David Eppstein addressed Spock of Vulcan's point that "all [his] professors say travelling salesperson." I'd add that Scott Aaronson refers to the problem as "travelling salesperson" on his website, the "Complexity Zoo," which is competing with Wikipedia as the best source on the web for open learning about NP hard problems, see http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#np. — Preceding unsigned comment added by 140.247.59.98 (talk) 13:07, 3 April 2012 (UTC)

Invariants?

I was hoping to find a collection of properties about the problem including invariants (for the problem, the solution, and their connection). I'm not even sure the appropriate name for these properties.

For example (an invariant on a problem and its solution), I am mostly certain that if you take the TSP weight cost matrix and multiply it by a positive number, the solution path (not the solution distance) remains the same. That is, let W be the TSP matrix, let a > 0, and S be the optimal path for the TSP with W. Then if solution(W)=S, then solution(a*W)=S. Intuitively it seems true (the optimal path is still the optimal path if all distances are doubled/halved), but I've not seen a proof.

First, is the above statement true? Secondly, where is a good source for several more invariants? Thank you. — Preceding unsigned comment added by 150.135.222.233 (talk) 19:31, 24 September 2012 (UTC)

TSP in NP

NP-complete problems must first be in complexity class NP. That means a proposed solution can be verified in polynomial time. For many NP-complete problems like the Boolean satisfiability problem, that easily seen. But it is not so obvious for TSP. I think the article should give some explanation.--agr (talk) 04:33, 18 February 2013 (UTC)

The relevevant sentence, in the first section, says "the decision version of the TSP (where, given a length L, the task is to decide whether any tour is shorter than L) belongs to the class of NP-complete problems" What about that do you find non-obvious? —David Eppstein (talk) 05:56, 18 February 2013 (UTC)

It's obvious now, thanks.--agr (talk) 02:04, 19 February 2013 (UTC)

Why is vehicle routing hard - a simple (and misleading!!!) explanation

The link entitled "Why is vehicle routing hard - a simple explanation" gives the reader the impression that TSP is hard BECAUSE there are exponentially many solutions. Of course, this is not the reason for its complexity. Can we remove this link or show why this explanation gives the wrong impression? AustinBuchanan (talk) 19:16, 22 May 2013 (UTC)

I agree. I've removed it. —David Eppstein (talk) 19:56, 22 May 2013 (UTC)

Software Implementation, based on Openstreetmap Data?

I wonder if there is any software implementation based on OSM data? Allegedly, MapPoint (TM) is able to compute TSP routes, but this is proprietary software. Thanks. — Preceding unsigned comment added by 77.8.103.194 (talk) 11:12, 28 May 2013 (UTC)

Problem with algorithm illustrations

While these illustrations are really nice to have, they are unfortunately incorrect, see File_talk:Bruteforce.gif. This obviously holds also for the other three gifs. If somebody wants to step up, I would welcome that, otherwise it seems to me they better get deleted as they perhaps do more harm than good. Seattle Jörg (talk) 12:49, 19 June 2013 (UTC)

Exponential or super-polynomial

The introduction states that since the decision version of TSP is NP-complete that "it is likely that the worst-case running time for any algorithm for the TSP increases exponentially with the number of cities." Should this be changed to super-polynomial? Or are we assuming the exponential time hypothesis holds as well? AustinBuchanan (talk) 22:53, 13 July 2013 (UTC)

Karpinski citations

Hi David,

The section I deleted contained the following citations (cite counts per google scholar):

(M. Karpinski) "8/7-Approximation Algorithm for (1,2)-TSP", 2006, 74 cites
(Karpinski, Lampis and Schmied) "New Inapproximability Bounds for TSP", 2013, 1 cite
(Karpinski & Schmied) "On Approximation Lower Bounds for TSP with Bounded Metrics", 2013, 5 cites
(Engebretsen & Karpinski) "TSP with bounded metrics", 2006, 19 cites
(Karpinski & Schmied) "Approximation Hardness of Graphic TSP on Cubic Graphs", 2013, 1 cite

The "8/7" paper might be worked in to the article, but the rest just haven't been cited often enough (in my opinion) to warrant specific mention. If it was just one or two papers I'd probably let it slide (and there re a few like that in this article), but with five papers with the same author it looks like someone (not necessarily Karpinski) is inflating Karpinski's reputation. I'd like to remove the paragraph and citations. Your thoughts? Lesser Cartographies (talk) 01:07, 30 July 2013 (UTC)

Ok, based on your analysis I agree that everything with single-digit citations should go. How about, as you suggest, deleting this paragraph, but then in the "complexity of approximation" section where it says the best ratio for 1,2-TSP is 7/6, change it to 8/7 and cite the 2006 paper? —David Eppstein (talk) 06:36, 30 July 2013 (UTC)

I think I managed to pull that off correctly, but please check my work. Lesser Cartographies (talk) 07:10, 30 July 2013 (UTC)

Modulo the fact that some citations have wandered into the notes section, standard citation formatting isn't followed, et cetera... ok, it's on my list. Lesser Cartographies (talk) 07:19, 30 July 2013 (UTC)

Indices of summation in ILP problem statement

Currently the integer programming problem statement is given as

{\begin{aligned}\min &\sum _{i\neq j}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&\forall i,j\\&x_{ij}{\text{ integer}}&\forall i,j\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&j=0,\ldots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&i=1,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&1\leq i\neq j\leq n\\u_{i}\geq 0&&1\leq i\leq n.\end{aligned}}

In the last two inequalities i and j go from 1 to n, and in the second set of equalities i goes from 1 to n. But in three places i and/or j goes from 0 to n. Should these three appearances of 0 be changed to 1? Duoduoduo (talk) 18:07, 9 August 2013 (UTC)

ILP Formulation: What is $u$ ?

The ILP formulation does not give any hints as to what $u$ corresponds to, which is confusing. Could someone who knows about this please add it to the ILP formulation? 115.113.149.70 (talk) 14:29, 16 August 2013 (UTC)

Euclidean TSP NP-Complete?

In the part about Euclidean TSP it says that both TSP and Euclidean TSP is NP-Complete.

I'm certain that TSP has not been shown to be NP-Complete since it would prove P=NP.

But I do not have the knowledge to wether it is true for Euclidean TSP as it is a special case and the reference is just pointing to a wiki page on the journal so I'm unable to verify the claim. — Preceding unsigned comment added by 62.84.214.2 (talk) 11:41, 22 September 2011 (UTC)

Been looking at it and it is problably a missunderstanding. TSP as defined here is not a decision problem so it can't be part of NP-Complete. Probably the paper is talking about the related decision problem which is NP-Complete. I will remove this part and the reference unless I hear something on this page.

In any case to be NP-complete it is necessary that the decision problem be in NP, which is not entirely clear in the Euclidean case due to the difficulty of comparing lengths of tours that are sums of square roots (using Pythagoras to compute distances). For this reason the Papadimitriou paper that we cite as a reference for this actually proves the completeness of (the decision version of) an approximation to the Euclidean TSP in which vertex coordinates are rational numbers and their distances are rounded down to the nearest smaller integer. But the same reduction also proves that the actual Euclidean TSP is NP-hard, so maybe that's the safest thing to say here. —David Eppstein (talk) 21:30, 22 September 2011 (UTC)

The article seems to be incorrect on this point. Garey and Johnson, who also use the Papadimitriou paper as a ref., say that the variant using discretized Euclidean metric is NP-complete and that the version with the non-discretized metric is not known to be in NP. Also the conclusion that this implies the metric version is NP-complete is wrong, we'd need to show that the graph could be embedded in the Euclidean plane and this isn't true. (In fact there are metric graphs that can't be embedded in any Euclidean space.) I'll try to rewrite that paragraph.--RDBury (talk) 18:34, 12 August 2013 (UTC)

This Wikipedia article states that TSP is NP complete. If this is only true for some restricted formulations of the problem, that statement should be changed. GreSebMic (talk) 09:41, 9 September 2013 (UTC)

Verifying desicion problem version?

Ok, I get that it's polynomial time to verify a yes answer to the decision problem version. But how do you check a no answer in polynomial time? 70.167.155.42 (talk) 01:39, 16 September 2013 (UTC)

You don't. If you could, TSP would be in co-NP, and NP would equal co-NP, a very unlikely scenario at least according to the conventional wisdom. —David Eppstein (talk) 01:53, 16 September 2013 (UTC)

Ilya Gazman's solution

Please take a look at this, is it possible that this solution is really $O(n2^{n})$ ?

This is not the place to discuss unpublished results. n2^n is not polynomial. And if you think you have found a polynomial solution, join the queue. —David Eppstein (talk) 17:50, 12 October 2013 (UTC)

Example solution images

Why isn't the solution shown in the example images like this? (ignore the distance, I just edited the path) — Preceding unsigned comment added by 86.163.197.192 (talk) 08:02, 24 November 2013 (UTC)

See below the section Problem with algorithm illustrations Seattle Jörg (talk) 08:25, 12 February 2014 (UTC)

Solution picture on wikipedia doesn't tell how that solution was got, i am very suspcious is it really shortest. Is example done with all possible outcomes using computer?

Lower bound

I can't remember enough about this theory to know whether the lower bound given below (removed from article) is valid or not, but it certainly needs clarifying and simplifying before being put back in the article.
Extend this idea. Suppose two movers stand on station j, one goes forward to visit few stations near j, the other goes backward to visit few stations near j. Soon one mover experienced that if he always visit the nearest station then he will lagged his partner. If we had ramdonly painted the N stations into 2 colors blue and red, and let one mover always visit nearest blue station, the other mover always visit nearest red station, then a mover will not lag his partner and we see ${\frac {2}{2}}{\sqrt {N/2}}$ is a still better lower bound. ^{[citation needed]}
Please could an expert check? Dbfirs 10:47, 16 February 2009 (UTC)

(later ...) Lingwanjae has kindly provided the following:

Suppose there are N stations in a square and a station named j. Suppose the shortest tour is known. A mover stands on j marchs forward N/2 stations according to tour and paints them into red. A mover stands on j marchs backward N/2 stations according to tour and paints them into blue.

Thus the neighjbors of j have half possibility in color red.

Let j's next station on the shortest tour is named k. So k is red.

So distance(j,k) = distance(j, some red neighbor) >= distance(j, nearest red neighbor)

So distance(j,k) >= distance(j, nearest red neighbor) =0.5/sqrt(N/2)=0.707/sqrt(N)

So whole tour length >= 0.707/sqrt(N)*N=sqrt(N/2)

I think it would be better to write the result as

0.7071{\sqrt {N}}

for easy comparison, but the argument convinces me. Does it need a citation? Dbfirs 20:55, 16 February 2009 (UTC)

The section "TSP path length" is still in a fairly bad shape. It does not state the setup clearly (Euclidean TSP, uniformly at random?). It states various bounds but does not make it explicit what they are (lower bound on the expected value? lower bound with a constant probability? lower bound with a high probability?). Furthermore, it seems to mix up theoretical lower bounds with some estimates that are based on computer experiments, even though the first paragraph talks about "theoratical low bounds". I would also split the first paragraph in two parts: first, explain the setup (what these bounds really are); second, explain how these can be used (e.g., evaluating the performance of TSP algorithms). — Miym (talk) 08:44, 17 February 2009 (UTC)

It occurred to me that we could also extend this section by presenting non-probabilistic bounds. For example, Few (1955): "The shortest path and the shortest road through n points", Mathematika 2:141–144, shows that there is always a path of length sqrt(2n)+1.75 through n ≥ 2 points, no matter how you place them in a unit square. Naturally this gives the upper bound sqrt(2n)+O(1) for the TSP tour as well. It is easy to give a proof that the upper bound is O(sqrt(n)) – simply partition the square into approx. sqrt(n) vertical stripes and sweep them one by one – and the proof could be sketched in the article as well (with an illustration). — Miym (talk) 09:27, 17 February 2009 (UTC)

I agree fully with your suggestions, Miym. I was hoping that you or some other expert would make the improvements. Dbfirs 18:09, 5 March 2009 (UTC)

The arguments don't seem correct, and I can't see how to make it so. If I got it right, you are implictly assuming that the N/2 first points in the salesman's path have the same distribution as N/2 independent uniform random points, which of course is not the case. Dralea (talk) 15:12, 11 July 2014 (UTC)

This whole section seemed incoherent, so I have replaced it with almost entirely different material. I hope that this is an improvement, but it could definitely use more work. Hack away freely. xnn (talk) 08:53, 8 June 2010 (UTC)

.

Workers chasing TSP lower bound and upper bound are working in a conviction that the exact solution is reachable. Once reached, human can measure how good an approximate solution is. So human can solve NP hard problem in linear time approximation and take precision under good control. Lingwanjae (talk) 15:02, 16 June 2010 (UTC)

I don't know what this paragraph is supposed to mean, but for points in the Euclidean plane a polynomial time approximation scheme for the TSP is already known, and for arbitrary metric spaces it's known that (unless P=NP) there's some constant factor beyond which it's not possible to approximate in polynomial time. —David Eppstein (talk) 15:15, 16 June 2010 (UTC)

Here's a link to my revision for ease of reference: http://en.wikipedia.org/w/index.php?title=Travelling_salesman_problem&oldid=366748617#Travelling_salesman_on_a_random_geometric_graph . I'll just reiterate that I don't understand this section as it is currently written. What is √(N/2) supposed to be a lower bound for? (It clearly isn't a lower bound for the length of tour of N points in the unit square.) Answering the "citation needed" tag that someone added would help. xnn (talk) 16:29, 16 June 2010 (UTC)

I think it is a lower bound for the expected value of the length of the TSP of N random points in the square. —David Eppstein (talk) 13:40, 17 June 2010 (UTC)

.

If 1000000 points are randomly distributed in a 1x1 square, then its shortest path length is between 0.707sqrt(1000000) and 0.710sqrt(1000000). So 0.707 is a lower bound. In the graph xnn illustrated the points are distributed on lattice not random so its length is 1sqrt(1000000). References are linked on wiki TSP page and the following is one of it.

http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf --- Lingwanjae (talk) 12:05, 18 June 2010 (UTC)

Thank you, I think I understand what the article is trying to say now: that with high probability the TS length is (c+o(1))√n, and the given values are experimental bounds on c. The material I added was just the crude bounds that I can prove. It would be useful to make explicit that we are bounding the expected length of the shortest tour, and also that there is concentration about the mean. xnn (talk) 13:22, 19 June 2010 (UTC)

This is a correct interpretation. I made this precise by stating first Beardwood, Halton & Hammersley's result: almost surely, the length is asymptotically equivalent to (c+o(1))√n, where c is a constant. I also included an elementary justification why bounding the expectation gives bounds on c. Dralea (talk) 15:17, 11 July 2014 (UTC)