Talk:Travelling salesman problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Computer science (Rated B-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
WikiProject Systems (Rated B-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
Taskforce icon
This article is within the field of Operations research.
 
edit·history·watch·refresh Stock post message.svg To-do list for Travelling salesman problem:

Here are some tasks awaiting attention:

Contents

Example solution images[edit]

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)

Lukas Roots's solution[edit]

Don't have any insight but this article claims a 16 year old 'solved' the problem... [1] --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)

Optimal solution for 15,112 cities[edit]

According to this link, [2], 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)

Princeton proof?[edit]

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)

General Case[edit]

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[edit]

"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)

Question[edit]

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)

a proposed algorithm[edit]

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)

Political Correctness[edit]

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.

subexp time for euclidian TSP ?[edit]

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)

two questions on higher-dimensional TSPs[edit]

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.

"Human performance"[edit]

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)

What about the ants?[edit]

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)

Polytime solution in progress?[edit]

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)

Spelling[edit]

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. [3] --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)

Political Correctness[edit]

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)

Nearest Neighbour Algorithm cannot find worst possible solution.[edit]

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[edit]

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?[edit]

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)

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

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)

Reference to MATLAB[edit]

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[edit]

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[edit]

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)

  • 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)

Optimization version NP-complete?[edit]

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[edit]

It's a pity that there is no article The travelling salesman problem in popular culture. It's probably too offtopic for this one: [4]. --Hans Adler (talk) 20:05, 27 March 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"[edit]

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

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

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?[edit]

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[edit]

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)

Lower bound[edit]

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)

Nearest Neighbor Algorithm[edit]

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 (talkcontribs) 17:47, 5 March 2009 (UTC)

Clarification for complexity analysis?[edit]

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 (talkcontribs) 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)

Page should be moved[edit]

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)

Example: Symmetric TSP with four cities[edit]

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[edit]

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)

The map of Germany shows too many cities[edit]

The disputed map

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) TSP tour from an 1832 book.svg

New Route For Tour of 15 German Cities[edit]

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 (talkcontribs) 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)

Linear Programing anyone?[edit]

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)

Hamiltonian Cycle?[edit]

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 Kn, 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?[edit]

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)

Euclidean TSP NP-Complete?[edit]

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)

Invariants?[edit]

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[edit]

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[edit]

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?[edit]

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[edit]

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[edit]

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[edit]

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[edit]

Currently the integer programming problem statement is given as


\begin{align}
\min & \sum_{i\ne j}c_{ij}x_{ij} & \\
0\le & x_{ij} \le 1  & \forall i,j  \\
& x_{ij} \text{ integer} & \forall i,j \\
& \sum_{i=0,i\ne j}^n x_{ij} = 1 &   j=0,\ldots,n \\
& \sum_{j=0,j\ne i}^n x_{ij} = 1 & i=1,\ldots,n \\
u_i-u_j & +nx_{ij} \le n-1 & 1 \le i \ne j \le n \\
u_i\geq 0 & & 1 \le i \le n.
\end{align}

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?[edit]

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)

ILP formulation always infeasible?[edit]

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{align}
& u_i-u_j+nx_{ij} \le n-1 & 1 \le i \ne j \le n
\end{align}

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{align}
u_1-u_2+nx_{1,2} & \le n-1 \\
u_1-u_2+2 \times 1 & \le 2-1 \\
u_1-u_2+2 & \le 1 \\
u_1-u_2 & \le 1-2 \\
u_1-u_2 & \le -1 \\
\end{align}

\begin{align}
u_2-u_1+nx_{2,1} & \le n-1 \\
u_2-u_1+2 \times 1 & \le 2-1 \\
u_2-u_1+2 & \le 1 \\
u_2-u_1 & \le 1-2 \\
u_2-u_1 & \le -1 \\
u_1-u_2 & \ge +1 \\
\end{align}

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 ui etc. in them don't involve u0: they are given as applying to 1 \le i \ne j \le 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{align}
u_1-u_2+nx_{1,2} & \le n-1 \\
u_1-u_2+3 \times 1 & \le 3-1 \\
u_1-u_2+3 & \le 2 \\
u_1-u_2 & \le 2-3 \\
u_1-u_2 & \le -1 \\
u_2-u_1 & \ge 1 \\
\end{align}

\begin{align}
u_2-u_1+nx_{2,1} & \le n-1 \\
u_2-u_1+3 \times 0 & \le 3-1 \\
u_2-u_1 & \le 2 \\
\end{align}

\begin{align}
u_2-u_3+nx_{2,3} & \le n-1 \\
u_2-u_3+3 \times 1 & \le 3-1 \\
u_2-u_3+3 & \le 2 \\
u_2-u_3 & \le 2-3 \\
u_2-u_3 & \le -1 \\
u_3-u_2 & \ge 1 \\
\end{align}

\begin{align}
u_3-u_2+nx_{3,2} & \le n-1 \\
u_3-u_2+3 \times 0 & \le 3-1 \\
u_3-u_2 & \le 2 \\
\end{align}

\begin{align}
u_3-u_1+nx_{3,1} & \le n-1 \\
u_3-u_1+3 \times 1 & \le 3-1 \\
u_3-u_1+3 & \le 2 \\
u_3-u_1 & \le 2-3 \\
u_3-u_1 & \le -1 \\
u_1-u_3 & \ge 1 \\
\end{align}

\begin{align}
u_1-u_3+nx_{1,3} & \le n-1 \\
u_1-u_3+3 \times 0 & \le 3-1 \\
u_1-u_3 & \le 2 \\
\end{align}
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 s2, s4, and s6), with a resulting zb 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 \ge 1, or u_1 \ge 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 0th 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 ith city to the jth city, I think that suggests there are n + 1 total cities, not n (i.e. the variable x_{0,n} indicates traversal from the 0th city to the nth; so for n=1, x_{0,1} indicates traversal from the 0th city to the 1st). 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 u0 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?[edit]

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 xij for i, j >0, so the proof that there can be no subtours does not work. In fact, setting all ui and uj 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[edit]

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} \ge 2 \delta_{ij} \le n-1 We have traveled forward more than one city
\delta_{ij} \ge 2-n \delta_{ij} \le -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} \ge 2 \delta_{ij} \le n-1 We have traveled forward more than one city
\delta_{ij} \ge 2-n \delta_{ij} \le -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} \ge 2-n \delta_{ij} \le 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} \ge 2-n 
\begin{align}
\delta_{ij} \ge 2-n + \begin{pmatrix} 1 - \begin{pmatrix} 2-n \end{pmatrix} \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ij} \ge 2-n + \begin{pmatrix} 1-2+n \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ij} \ge 2-n + \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \quad & \forall j>1 \\
-\delta_{ij} \le -2+n - \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ji} + \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \le n-2 \quad & \forall j>1
\end{align}

\begin{align}
\delta_{ij} \ge 2-n + \begin{pmatrix} 1-n - \begin{pmatrix} 2-n \end{pmatrix} \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \ge 2-n + \begin{pmatrix} 1-n-2+n \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \ge 2-n + \begin{pmatrix} -1 \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \ge 2-n - x_{ij} \quad & \forall j=1 \\
-\delta_{ij} \le -2+n + x_{ij} \quad & \forall j=1 \\
\delta_{ji} - x_{ij} \le n-2 \quad & \forall j=1
\end{align}
\delta_{ij} \le n-1 
\begin{align}
\delta_{ij} \le n-1 + \begin{pmatrix} 1 - \begin{pmatrix} n-1 \end{pmatrix} \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ij} \le n-1 + \begin{pmatrix} 1-n+1 \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ij} \le n-1 + \begin{pmatrix} 2-n \end{pmatrix} x_{ij} \quad & \forall j>1 \\
\delta_{ij} - \begin{pmatrix} 2-n \end{pmatrix} x_{ij} \le n-1 \quad & \forall j>1 \\
\delta_{ij} + \begin{pmatrix} n-2 \end{pmatrix} x_{ij} \le n-1 \quad & \forall j>1
\end{align}

\begin{align}
\delta_{ij} \le n-1 + \begin{pmatrix} 1-n - \begin{pmatrix} n-1 \end{pmatrix} \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \le n-1 + \begin{pmatrix} 1-n - n+1 \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \le n-1 + \begin{pmatrix} 2-2n \end{pmatrix} x_{ij} \quad & \forall j=1 \\
\delta_{ij} \le 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} \le n-1 \quad & \forall j=1 \\
\delta_{ij} + 2 \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \le n-1 \quad & \forall j=1
\end{align}

Substituting u_j-u_i for \delta_{ij}, I now have four constraints.


\begin{align}
u_i-u_j + \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \le n-2 \quad \forall j>1 \\
u_i-u_j - x_{ij} \le n-2 \quad \forall j=1 \\
u_j-u_i + \begin{pmatrix} n-2 \end{pmatrix} x_{ij} \le n-1 \quad \forall j>1 \\
u_j-u_i + 2 \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \le n-1 \quad \forall j=1
\end{align}

Or after some finagling:


\begin{align}
u_i-u_j - x_{ij} + \begin{pmatrix} nx_{ij} \text{ when } j>1 \end{pmatrix} & \le n-2 \\
u_j-u_i + \begin{pmatrix} n-2 \end{pmatrix} x_{ij} + \begin{pmatrix} nx_{ij} \text{ when } j=1 \end{pmatrix} & \le n-1
\end{align}

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 \le n \le 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} \le n-2 \quad \forall i \in 1 \ldots n  \,

 

 

 

 

(4)

u_i-u_j + \begin{pmatrix} n-1 \end{pmatrix} x_{ij} \le n-2 \quad \begin{matrix} \forall i \in 1 \ldots n \\ \forall j \in 2 \ldots n \end{matrix} \,

 

 

 

 

(5)

\text{and}

0 \le x_{ij} \le 1 \quad x_{ij} \in \mathbb{Z} \,

 

 

 

 

(6)

u_i \ge 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} \ge 1-n We have not traveled forward one city

(Its worth noting that we ignored the \delta_{ij} \le 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} \ge 1-n 
\begin{matrix}
\delta_{ij} \ge 1-n + \begin{pmatrix} 1 - \begin{pmatrix} 1-n \end{pmatrix} \end{pmatrix} x_{ij} \\
\delta_{ij} \ge 1-n + \begin{pmatrix} 1-1+n \end{pmatrix} x_{ij} \\
\delta_{ij} \ge 1-n + \begin{pmatrix} n \end{pmatrix} x_{ij} \\
\delta_{ij} \ge 1-n + nx_{ij} \\
-\delta_{ij} \le -1+n - nx_{ij} \\
\delta_{ji} + nx_{ij} \le n-1 \\
\end{matrix}

Substituting u_j-u_i for \delta_{ij}, again just like last time...

u_i-u_j + nx_{ij} \le 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[edit]

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} \le n-1 \quad \begin{align} & \forall i \in 0 \ldots n-1 \\ & \forall j \in 1 \ldots n \end{align} \,

 

 

 

 

(4)

\text{and}

0 \le x_{ij} \le 1 \quad x_{ij} \in \mathbb{Z} \,

 

 

 

 

(5)

u_i \ge 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)[edit]

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  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?[edit]

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{align}
0 \leq x_{ij} \leq 1 \\
\end{align}
since sub-tours like those in Fig. 26-3-IV [omitted] also satisfy the conditions. However, if so-called loop conditions like

\begin{align}
x_{12} + x_{23} + x_{31} \leq 2
\end{align}
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[1] 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)

Verifying desicion problem version?[edit]

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[edit]

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)

constraints on u_i needed, or helpful to state?[edit]

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{align}
\min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} & \\
0\le & x_{ij} \le 1  & i,j=0, \dots n  \\
& x_{ij} \text{ integer} & i,j=0, \dots n \\
& \sum_{i=0,i\ne j}^n x_{ij} = 1 &   j=0,\ldots,n \\
& \sum_{j=0,j\ne i}^n x_{ij} = 1 & i=1,\ldots,n \\
u_i-u_j & +nx_{ij} \le n-1 & 1 \le i \ne j \le n.
\end{align}

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.

  1. ^ http://www.unc.edu/~pataki/papers/teachtsp.pdf