Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
mNo edit summary
No edit summary
 
(149 intermediate revisions by 89 users not shown)
Line 1: Line 1:
{{WikiProjectBannerShell|1=
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.
{{WikiProject Computer science |class=B |importance=top}}
{{maths rating|frequentlyviewed=yes|importance=Mid|field=discrete|class=B}}
{{Sys rating |class=B |importance=high |field=Operations research}}
}}
{{todo}}


== Example solution images ==
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


Why isn't the solution shown in the example images [http://i.imgur.com/W0FjO0j.gif like this]? (ignore the distance, I just edited the path)  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.163.197.192|86.163.197.192]] ([[User talk:86.163.197.192|talk]]) 08:02, 24 November 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
Registered users will be able to choose between the following three rendering modes:  
: See below the section Problem with algorithm illustrations [[User:Seattle Jörg|Seattle Jörg]] ([[User talk:Seattle Jörg|talk]]) 08:25, 12 February 2014 (UTC)


== Lukas Roots's solution ==
'''MathML'''
Don't have any insight but this article claims a 16 year old 'solved' the problem... [http://www.contracostatimes.com/mld/cctimes/email/news/14410404.htm] --[[User:67.187.48.82|67.187.48.82]] 04:18, 27 April 2006 (UTC)
:<math forcemathmode="mathml">E=mc^2</math>
: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. --[[User:Abelani|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.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/140.247.43.99|140.247.43.99]] ([[User talk:140.247.43.99|talk]]) 00:52, 3 September 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->


== Optimal solution for 15,112 cities ==
<!--'''PNG'''  (currently default in production)
According to this link, [http://www.math.princeton.edu/tsp/d15sol/], an optimal solution has been found for the 15,112 city problem, not just an approximate solution. --[[User:Petero2|Petero2]] 16:33 Jan 31, 2003 (UTC)
:<math forcemathmode="png">E=mc^2</math>


-- 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. ---[[User:Smremde|Smremde]] 11:58, 25 July 2006 (UTC)
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


== Princeton proof? ==
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


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,
==Demos==
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".
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


Colin M Davidson


----
* accessibility:
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


:''How fast are the best known deterministic algorithms?''
==Test pages ==


To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


----
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
"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?"
==Bug reporting==
 
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
Shouldn't it be "... that visits each city '''once''' ..."?
:Yes. Thanks. [[User:Mikkalai|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 [[User:Nr9|Nr9]] 08:14, 8 April 2006 (UTC)
 
== 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". [[User:Bo Jacoby|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.  [[User:Cgray4|Cgray4]] 09:51, 4 April 2006 (UTC)
 
== Question ==
 
<div style="border: 1px solid #aaaaaa; background-color: #fff; margin: 0.5em 2em 0.5em 2em; padding: .2em;">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).</div>
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? —[[User:Simetrical|Simetrical]] ([[User talk:Simetrical|talk]]&nbsp;•&nbsp;[[Special:Contributions/Simetrical|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. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 06:56, 21 September 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.
[[User:Honnza|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. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 06:53, 21 September 2006 (UTC)
 
== Political Correctness ==
 
Should this be Traveling Salesperson Problem? I seem to remember it being changed
 
--[[User:143.53.132.154|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.
--[[User:85.127.5.34|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 ? ==
 
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. --[[User:68.61.203.204|68.61.203.204]] 18:47, 26 November 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? --[[User:Ixfd64|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" ==
 
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]] (<small>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  </small>).
*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. `'[[user:mikkalai|mikka]] 16:32, 2 January 2007 (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.
[[User:81.156.221.243|81.156.221.243]] 16:35, 3 February 2007 (UTC)Sabita Banerji
 
Is there a reference to this? [[Special:Contributions/194.237.142.10|194.237.142.10]] ([[User talk:194.237.142.10|talk]]) 13:35, 30 September 2008 (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? [[User:140.247.40.63|140.247.40.63]] 09:16, 4 February 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. --[[User:Thisisbossi|Thisisbossi]] 22:42, 7 February 2007 (UTC)
 
:There are two ls in travelling.  The verb is "to travel", not "to travele". [[User:Paul Silverman|Paul Silverman]] 19:41, 8 February 2007 (UTC)
 
::One L as per Merriam-Webster. [http://mw1.merriam-webster.com/dictionary/travelling] --[[User:Thisisbossi|Thisisbossi]] 22:12, 8 February 2007 (UTC)
 
::: Miriam Webster is rubbish [http://www.askoxford.com/concise_oed/travel Oxford spells it properly]. [[User:Paul Silverman|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. --[[User:Thisisbossi|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. -[[User:SpuriousQ|SpuriousQ]] ([[User talk: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 -- [[User:Jokes Free4Me|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.
[[User:Psy wombats|Psy wombats]] 14:46, 23 October 2007 (UTC)
 
== Political Correctness ==
 
I agree and accordingly corrected the notes. <small>—The preceding [[Wikipedia:Sign your posts on talk pages|unsigned]] comment was added by [[Special:Contributions/89.243.66.153|89.243.66.153]] ([[User talk:89.243.66.153|talk]]) 16:20, 4 March 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->
 
Can we change the traveling salesMAN problem to the traveling salesPERSON problem?  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/192.52.218.45|192.52.218.45]] ([[User talk:192.52.218.45|talk]]) 00:14, 4 June 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
 
== 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 [ [[User_Talk: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?--[[User:Kjells|Kjells]] 18:40, 25 April 2007 (UTC)
 
:Consider simulating to get an idea. It seems it should probably be exponentially small.[[User:Ninjagecko|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)''. <small>—The preceding [[Wikipedia:Sign your posts on talk pages|unsigned]] comment was added by [[Special:Contributions/143.239.1.153|143.239.1.153]] ([[User talk:143.239.1.153|talk]]) 19:33, 1 May 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->
 
: 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. [[User:Ninjagecko|Ninjagecko]] 12:41, 8 May 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. [[User:Ninjagecko|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.--[[User:Kjells|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. [[User:David.hillshafer|David Hillshafer]] 23:10, 24 August 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. <small>—The preceding [[Wikipedia:Sign your posts on talk pages|unsigned]] comment was added by [[Special:Contributions/62.56.77.207|62.56.77.207]] ([[User talk:62.56.77.207|talk]]) 15:15, 11 May 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->
 
== 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. [[User:Cngoulimis|Cngoulimis]] 11:00, 16 July 2007 (UTC)
:I rewrote and moved this section. [[User:Dcoetzee|Dcoetzee]] 23:02, 7 August 2007 (UTC)
 
==Contested move request==
<!--Template:WP:RMC-->''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 [[Wikipedia:Requested moves#Requesting potentially controversial moves|full request]] is not lodged within five days of this request being contested, the request will be removed from WP:RM.''  —[[User:Stemonitis|Stemonitis]] 06:27, 11 August 2007 (UTC)<noinclude>
*'''[[:Travelling salesman problem]] → [[:Traveling salesman problem]]''' — spelling ——[[User:Disavian|Disavian]] ([[User talk:Disavian|<sup>talk</sup>]]/[[Special:Contributions/Disavian|<sub>contribs</sub>]]) 19:53, 10 August 2007 (UTC)
:*[[WP:ENGVAR]] explicitly forbids this kind of switching between US and Commonwealth spellings. --[[User:Stemonitis|Stemonitis]] 06:27, 11 August 2007 (UTC)
:*Yes, this should clearly stay where it is, unless a compelling reason to do otherwise is raised. [[User:Dcoetzee|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 "trave'''ll'''ing" then all instances of the word should be spelled that way in the article. —[[User:Disavian|Disavian]] ([[User talk:Disavian|<sup>talk</sup>]]/[[Special:Contributions/Disavian|<sub>contribs</sub>]]) 17:34, 11 August 2007 (UTC)
:::*...Which looks like it was done after I submitted my request. Excellent. —[[User:Disavian|Disavian]] ([[User talk:Disavian|<sup>talk</sup>]]/[[Special:Contributions/Disavian|<sub>contribs</sub>]]) 17:35, 11 August 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? [[User:77.49.167.219|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. [[User:Dcoetzee|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: [http://www.xkcd.org/399/]. --[[User:Hans Adler|Hans Adler]] ([[User talk: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" ==
 
Is there any proof or analysis about this? Thanks.[[User:Ifcongif|Ifcongif]] ([[User talk:Ifcongif|talk]]) 01:57, 11 November 2008 (UTC)
* see [[Hamiltonian path problem]]. `'[[user:mikkalai|Míkka]][[user talk:mikkalai|>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.[[User:Ifcongif|Ifcongif]] ([[User talk: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. [[User:Dcoetzee|Dcoetzee]] 02:01, 18 November 2008 (UTC)
 
 
Thank you very much.[[User:Ifcongif|Ifcongif]] ([[User talk: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? [[Special:Contributions/70.251.156.117|70.251.156.117]] ([[User talk: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. [[User:Thore Husfeldt|Thore Husfeldt]] ([[User talk:Thore Husfeldt|talk]]) 21:25, 19 January 2009 (UTC)
 
== 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.  <br>
''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 <math>\frac{2}{2} \sqrt{N/2}</math> is a still better lower bound. {{fact|date=February 2009}}'' <br>
Please could an expert check?  [[User:Dbfirs|''<font face="verdana"><font color="blue">D</font><font color="#00ccff">b</font><font color="#44ffcc">f</font><font color="66ff66">i</font><font color="44ee44">r</font><font color="44aa44">s</font></font>'']] 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 <math>0.7071\sqrt{N}</math> for easy comparison, but the argument convinces me.  Does it need a citation?  [[User:Dbfirs|''<font face="verdana"><font color="blue">D</font><font color="#00ccff">b</font><font color="#44ffcc">f</font><font color="66ff66">i</font><font color="44ee44">r</font><font color="44aa44">s</font></font>'']] 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). — [[User:Miym|Miym]] ([[User talk: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). — [[User:Miym|Miym]] ([[User talk: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.  [[User:Dbfirs|''<font face="verdana"><font color="blue">D</font><font color="#00ccff">b</font><font color="#44ffcc">f</font><font color="66ff66">i</font><font color="44ee44">r</font><font color="44aa44">s</font></font>'']] 18:09, 5 March 2009 (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. [[User:Xnn|xnn]] ([[User talk: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. [[User:Lingwanjae|Lingwanjae]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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 &radic;(''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. [[User:Xnn|xnn]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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 --- [[User:Lingwanjae|Lingwanjae]] ([[User talk: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. [[User:Xnn|xnn]] ([[User talk:Xnn|talk]]) 13:22, 19 June 2010 (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?
[[User:Padde|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.  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Lingwanjae|Lingwanjae]] ([[User talk:Lingwanjae|talk]] • [[Special:Contributions/Lingwanjae|contribs]]) 17:47, 5 March 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
 
== 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.  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Skytopia|Skytopia]] ([[User talk:Skytopia|talk]] • [[Special:Contributions/Skytopia|contribs]]) 01:10, 10 July 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
 
: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]]. —[[User:David Eppstein|David Eppstein]] ([[User talk: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).--[[User:Skytopia|Skytopia]] ([[User talk: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. [[User:Thore Husfeldt|Thore Husfeldt]] ([[User talk: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.--[[User:Skytopia|Skytopia]] ([[User talk:Skytopia|talk]]) 01:10, 12 July 2009 (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. [[User:Spock of Vulcan|Spock of Vulcan]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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. [[User:Dcoetzee|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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/140.247.59.98|140.247.59.98]] ([[User talk:140.247.59.98|talk]]) 13:07, 3 April 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
== 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. [[User:Vadigor|Vadigor]] ([[User talk: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 [[Special:Contributions/132.161.224.94|132.161.224.94]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 07:31, 30 January 2010 (UTC)
 
== The map of Germany shows too many cities ==
[[File:TSP Deutschland 3.png|thumb|right|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).
 
[[User:FvdP|--FvdP]] ([[User talk: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. &nbsp;--[[User talk:Lambiam|Lambiam]] 00:59, 12 March 2011 (UTC)
:I agree, should be corrected! --[[User:Fioravante Patrone|Fioravante Patrone]] ([[User talk: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... --[[User:Fioravante Patrone|Fioravante Patrone]] ([[User talk: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. --[[User:Kapitän Nemo from DE|Kapitän Nemo from DE]] ([[User talk: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: [http://www.scuderialabellaria.it/TSP_Deutschland_7.png]. 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. --[[User:Fioravante Patrone|Fioravante Patrone]] ([[User talk: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. [[User:Thore Husfeldt|Thore Husfeldt]] ([[User talk:Thore Husfeldt|talk]]) 11:53, 14 March 2011 (UTC) [[File:TSP_tour_from_an_1832_book.svg]]
 
== 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.  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:South Texas Waterboy|South Texas Waterboy]] ([[User talk:South Texas Waterboy|talk]] • [[Special:Contributions/South Texas Waterboy|contribs]]) 05:31, 10 July 2010 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
 
: 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.
 
: -- [[User:Kapitän Nemo from DE|Kapitän Nemo from DE]] ([[User talk:Kapitän Nemo from DE|talk]]) 17:27, 15 March 2011 (UTC)
 
== Linear Programing anyone? ==
 
This problem can be solved easily by using linear programing.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/210.4.96.72|210.4.96.72]] ([[User talk:210.4.96.72|talk]]) 23:46, 5 October 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
 
:Congratulations! Your discovery will win you a [[Millennium Prize Problems#P versus NP|Millennium Prize]]. Please consider donating some of the prize money to the [[Wikimedia Foundation]]. &nbsp;--[[User talk:Lambiam|Lambiam]] 01:02, 9 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.  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/108.114.86.19|108.114.86.19]] ([[User talk:108.114.86.19|talk]]) 22:48, 11 April 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: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 {{mvar|n}}-vertex graph {{mvar|G}} has a Hamiltonian cycle if and only if the [[complete graph]] {{math|''K<sub>n</sub>''}}, with edge lengths equal to one for edges in {{mvar|G}} and two otherwise, has a traveling salesman tour of length at most {{mvar|n}}. I guess the description in the present article has it kind of muddled; it could use improvement. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 23:05, 11 April 2011 (UTC)
 
== Conversion to symmetric TSP: OR? ==
 
The section [[Travelling salesman problem#Solving by conversion to symmetric TSP|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<nowiki>'</nowiki>''{{·}}''C''{{·}}''A<nowiki>'</nowiki>''{{·}}''D''{{·}}''C<nowiki>'</nowiki>''{{·}}''B''{{·}}''D<nowiki>'</nowiki>''{{·}}''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 [[WP:original research|original research]]. &nbsp;--[[User talk:Lambiam|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<nowiki>'</nowiki>''{{·}}''C''{{·}}''A<nowiki>'</nowiki> 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
[[Special:Contributions/122.57.158.46|122.57.158.46]] ([[User talk:122.57.158.46|talk]]) 05:51, 3 June 2011 (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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/62.84.214.2|62.84.214.2]] ([[User talk:62.84.214.2|talk]]) 11:41, 22 September 2011 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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.--[[User:RDBury|RDBury]] ([[User talk: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. [[User:GreSebMic|GreSebMic]] ([[User talk:GreSebMic|talk]]) 09:41, 9 September 2013 (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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/150.135.222.233|150.135.222.233]] ([[User talk:150.135.222.233|talk]]) 19:31, 24 September 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
== TSP in NP ==
 
NP-complete problems must first be in [[NP (complexity)|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.--[[User:ArnoldReinhold|agr]] ([[User talk:ArnoldReinhold|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? —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 05:56, 18 February 2013 (UTC)
::It's obvious now, thanks.--[[User:ArnoldReinhold|agr]] ([[User talk:ArnoldReinhold|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? [[User:AustinBuchanan|AustinBuchanan]] ([[User talk:AustinBuchanan|talk]]) 19:16, 22 May 2013 (UTC)
:I agree. I've removed it. —[[User:David Eppstein|David Eppstein]] ([[User talk: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.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/77.8.103.194|77.8.103.194]] ([[User talk:77.8.103.194|talk]]) 11:12, 28 May 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
== 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. [[User:Seattle Jörg|Seattle Jörg]] ([[User talk: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? [[User:AustinBuchanan|AustinBuchanan]] ([[User talk:AustinBuchanan|talk]]) 22:53, 13 July 2013 (UTC)
 
== Karpinski citations ==
 
Hi [[User:David Eppstein|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'''
* ('''Karpinsk'''i, 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?  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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? —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 06:36, 30 July 2013 (UTC)
::I think I managed to pull that off correctly, but please check my work.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 07:10, 30 July 2013 (UTC)
::<small>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.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 07:19, 30 July 2013 (UTC)</small>
 
== Indices of summation in ILP problem statement ==
 
Currently the integer programming problem statement is given as
 
: <math>
\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} 
</math>
 
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? [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 18:07, 9 August 2013 (UTC)
 
== ILP Formulation: What is <math>u</math>? ==
 
The ILP formulation does not give any hints as to what <math>u</math> corresponds to, which is confusing. Could someone who knows about this please add it to the ILP formulation?
[[Special:Contributions/115.113.149.70|115.113.149.70]] ([[User talk:115.113.149.70|talk]]) 14:29, 16 August 2013 (UTC)
 
== ILP formulation always infeasible? ==
 
Maybe I am missing something.  In the ILP formulation, I don't believe the last set of constraints can ever be feasible.  The constraints I suspect are invalid are the following, which are supposed to ensure a single tour.
 
: <math>
\begin{align}
& u_i-u_j+nx_{ij} \le n-1 & 1 \le i \ne j \le n
\end{align}
</math>
 
Consider the trivial case of two cities.  The only solution in this case (excluding these constraints) is <math>x_{1,2}=1</math> and <math>x_{2,1}=1</math> (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):
 
{| style="width: 100%"
| <math>
\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}
</math>
| <math>
\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}
</math>
|}
 
In other words, <math>u_1-u_2</math> must be less than <math>-1</math> and greater than <math>+1</math>, 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?  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 21:49, 29 August 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
 
: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'', <math>x_{ij}</math> and <math>x_{ji}</math> 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. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 12:24, 30 August 2013 (UTC)
 
::It appears to me that one of the cities is supposed to be indexed as 0, in which case the problem of false infeasibility does not arise because the constraints with ''u''<sub>''i''</sub> etc. in them don't involve ''u''<sub>0</sub>: they are given as applying to <math>1 \le i \ne j \le n</math>. For example, in the two-city case with cities 0 and 1, the constraints disappear entirely. [[User:Duoduoduo|Duoduoduo]] ([[User talk: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 <math>x_{1,2}=x_{2,3}=x_{3,1}=1</math>, <math>x_{2,1}=x_{3,2}=x_{1,3}=0</math>, and <math>n=3</math>.  We can simplify the suspect constraints as follows:
 
::::{| style="width: 100%" | class="wikitable"
| <math>
\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}
</math>
|| <math>
\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}
</math>
|-
| <math>
\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}
</math>
|| <math>
\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}
</math>
|-
| <math>
\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}
</math>
|| <math>
\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}
</math>
|}
 
:::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):
 
::::{|
|-
!scope="col" width="25px"|Z
!scope="col" width="25px"|u{{sub|1}}
!scope="col" width="25px"|u{{sub|2}}
!scope="col" width="25px"|u{{sub|3}}
!scope="col" width="25px"|s{{sub|1}}
!scope="col" width="25px"|s{{sub|2}}
!scope="col" width="25px"|s{{sub|3}}
!scope="col" width="25px"|s{{sub|4}}
!scope="col" width="25px"|s{{sub|5}}
!scope="col" width="25px"|s{{sub|6}}
!scope="col" width="25px"|b
|- align="center"
|  1 ||  0 ||  0 ||  0 || -1 ||  1 || -1 ||  1 || -1 ||  1 ||  9
|- align="center"
|  0 || -1 ||  1 ||  0 || -1 ||  0 ||  0 ||  0 ||  0 ||  0 ||  1
|- align="center"
|  0 || -1 ||  1 ||  0 ||  0 ||  1 ||  0 ||  0 ||  0 ||  0 ||  2
|- align="center"
|  0 ||  0 || -1 ||  1 ||  0 ||  0 || -1 ||  0 ||  0 ||  0 ||  1
|- align="center"
|  0 ||  0 || -1 ||  1 ||  0 ||  0 ||  0 ||  1 ||  0 ||  0 ||  2
|- align="center"
|  0 ||  1 ||  0 || -1 ||  0 ||  0 ||  0 ||  0 || -1 ||  0 ||  1
|- align="center"
|  0 ||  1 ||  0 || -1 ||  0 ||  0 ||  0 ||  0 ||  0 ||  1 ||  2
|}
 
:::This tableau can be solved in three pivots (on s{{sub|2}}, s{{sub|4}}, and s{{sub|6}}), with a resulting z{{sub|b}} of 3, indicating there is no feasible solution.  See what I meant when I said more than two cities wasn't as obviously incorrect?  :-)  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk: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 <math>u_1 - u_3 \ge 1</math>, or <math>u_1 \ge u_3 + 1</math>.  Subtracting one from the RHS only weakens the constraint, so we know <math>u_1 > u_3</math>.  Following this pattern on all three constraints from the left above, we get <math>u_1 > u_3</math>, <math>u_2 > u_1</math>, and <math>u_3 > u_2</math>.  Obviously, all three of these constraints cannot be true.  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk: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. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 19:22, 3 September 2013 (UTC)
{{od}}
I transcribed the relevant section from Dantzig 1963 [[User:Lesser Cartographies/sandbox/TSP notes|here]].  The third formulation looks to be what we want.  Dantzig cites this formulation to an IBM technical report:  {{citation|last=Tucker|first=A. W. | title=On Directed Graphs and Integer Programs | journal=IBM Mathematical research Project|publisher=Princeton University|year=1960}}.  Let me know if something appears nonsensical; I expect I made a few transcription errors.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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. [[User:Duoduoduo|Duoduoduo]] ([[User talk: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. [[User:Duoduoduo|Duoduoduo]] ([[User talk: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.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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.)  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 16:43, 4 September 2013 (UTC)
 
::::Thank you from me too, Lesser Cartographies.  I guess I am still confused over a couple points though.  First, as I think Duoduoduo pointed out above, its unusual that the single entry/single exit constraints don't apply to the 0{{sup|th}} city.
 
::::Second, if the range of <math>i</math> and <math>j</math> really is <math>0 \ldots n</math>, then that means both can take on <math>n + 1</math> unique values.  Given that <math>x_{i,j}</math> indicates traversal from the i{{sup|th}} city to the j{{sup|th}} city, I think that suggests there are <math>n + 1</math> total cities, not <math>n</math> (i.e. the variable <math>x_{0,n}</math> indicates traversal from the 0{{sup|th}} city to the n{{sup|th}}; so for <math>n=1</math>, <math>x_{0,1}</math> indicates traversal from the 0{{sup|th}} city to the 1{{sup|st}}).  This differs from the definition given for the first formulation you transcribed, and I doubt the single tour constraints expect this (although I don't know for sure).  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 16:52, 4 September 2013 (UTC)
 
:::::Regarding your second point, there are definitely ''n''+1 cities in this formulation. I tried to make that clear in line 2 of the text, saying "for cities 0, ..., ''n''". This contrivance of using ''n''+1 cities but not having a dummy variable ''u''<sub>0</sub> is what makes the single tour constraint work. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 18:02, 4 September 2013 (UTC)
 
===Should there also be adding-up constraints for i,j =0?===
 
Thanks, Lesser Cartographies, for checking that. It seems clear to me that the equations have to be made to hold for all of ''j''=0, 1, ... and ''i''= 0, 1, .... If not, the constraints permit tours of the form (e.g. for 5 cities with ''n''=4) 0→1→0→2→0→3→0→4→0. Here there are no non-zero ''x''<sub>''ij''</sub> for ''i'', ''j'' >0, so the proof that there can be no subtours does not work. In fact, setting all ''u''<sub>''i''</sub> and ''u''<sub>''j''</sub> 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. [[User:Duoduoduo|Duoduoduo]] ([[User talk: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.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 03:47, 6 September 2013 (UTC)
 
:So let's start by numbering the equations.
 
:<math>
\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}
</math>
 
: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:
::<math>e)\ </math>Choose <math>u_{i}=t</math> if city <math>i</math> is visited on the <math>t^{\rm{th}}</math> step where <math>t=1, 2, \ldots, n</math>.
:then <math>u_{i}</math> can never be greater than <math>n</math>.  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?  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 07:00, 6 September 2013 (UTC)  <small>If anyone can show me a reasonable way of numbering equations without horking the alignment, I'd be much obliged.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 07:02, 6 September 2013 (UTC) </small>
::<small>It horks the alignment, but I believe [[Help:Displaying_a_formula#Equation_numbering|this is how they expect you to number equations on Wikipedia]].  It at least lets you use the {{t1|EquationNote}} syntax elsewhere.  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 13:42, 6 September 2013 (UTC)<small>
:::<small>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.  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 13:46, 6 September 2013 (UTC)</small>
::::<small>Thank you!  <nowiki>\begin{array}</nowiki> did the trick.  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk:Lesser Cartographies|talk]]) 14:54, 6 September 2013 (UTC)</small>
 
:::::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. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 15:21, 6 September 2013 (UTC)
 
===An attempt to derive the invalid constraints===
I attempted to derive the last constraint from scratch.  I came up with something, but I skipped some steps, and I didn't prove anything.  I thought this could be useful for someone to gain some insight on the problem.
 
I made the assumption that <math>u_i</math> is defined as the index in which city <math>i</math> is visited.  This means <math>\delta_{ij}=u_j-u_i</math> can be defined as the number of steps to travel from city <math>i</math> to city <math>j</math>, 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, <math>\delta_{ij} = -\delta_{ji}</math>.
 
I'm also assuming <math>n</math> is the number of cities (as one might expect), and that <math>i \in 1 \ldots n</math>.
 
{|class="wikitable"
|-
!If...
!colspan="2"|One of must be true...
!Because...
|-
|rowspan="2"|<math>x_{ij}=1</math>
|colspan="2"|<math>\delta_{ij}=1</math>
|We have traveled forward one city
|-
|colspan="2"|<math>\delta_{ij}=1-n</math>
|We have traveled from the last city back to the first
|-
|rowspan="3"|<math>x_{ij}=0</math>
|<math>\delta_{ij} \ge 2</math>
|<math>\delta_{ij} \le n-1</math>
|We have traveled forward more than one city
|-
|<math>\delta_{ij} \ge 2-n</math>
|<math>\delta_{ij} \le -1</math>
|We have traveled backward
|-
|colspan="2"|<math>\delta_{ij}=0</math>
|We have not traveled
|-
|}
 
(By the way, I suspect the issue with the current formulation resulting in infeasibility is an attempt to handle both <math>x_{ij}=1</math> cases with <math>\delta_{ij}=1</math>.  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 <math>j=1</math> 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.
 
{|class="wikitable"
|-
!If...
!colspan="2"|One of must be true...
!Because...
|-
|rowspan="2"|<math>x_{ij}=1</math>
|<math>\delta_{ij}=1</math>
|<math>j>1</math>
|We have traveled forward one city
|-
|<math>\delta_{ij}=1-n</math>
|<math>j=1</math>
|We have traveled from the last city back to the first
|-
|rowspan="3"|<math>x_{ij}=0</math>
|<math>\delta_{ij} \ge 2</math>
|<math>\delta_{ij} \le n-1</math>
|We have traveled forward more than one city
|-
|<math>\delta_{ij} \ge 2-n</math>
|<math>\delta_{ij} \le -1</math>
|We have traveled backward
|-
|colspan="2"|<math>\delta_{ij}=0</math>
|We have not traveled
|-
|}
 
Next, I relaxed the <math>x_{ij}=0</math> case to just include the whole range.
 
{|class="wikitable"
|-
!If...
!colspan="2"|One of must be true...
!Because...
|-
|rowspan="2"|<math>x_{ij}=1</math>
|<math>\delta_{ij}=1</math>
|<math>j>1</math>
|We have traveled forward one city
|-
|<math>\delta_{ij}=1-n</math>
|<math>j=1</math>
|We have traveled from the last city back to the first
|-
|rowspan="1"|<math>x_{ij}=0</math>
|<math>\delta_{ij} \ge 2-n</math>
|<math>\delta_{ij} \le n-1</math>
|We have not traveled from the last city back to the first
|-
|}
 
Now I attempted to linearly combine the value of <math>x_{ij}=1</math> constraints with those in <math>x_{ij}=0</math> using the value of <math>x_{ij}</math>...
 
{|class="wikitable"
|-
!colspan="2" rowspan="2"|
!colspan="2"|<math>x_{ij}=1</math>
|-
!<math>\delta_{ij}=1 \quad \forall j>1</math>
!<math>\delta_{ij}=1-n \quad \forall j=1</math>
|-
!rowspan="2"|<math>x_{ij}=0</math>
!<math>\delta_{ij} \ge 2-n</math>
|<math>
\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}
</math>
|<math>
\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}
</math>
|-
!<math>\delta_{ij} \le n-1</math>
|<math>
\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}
</math>
|<math>
\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}
</math>
|-
|}
 
Substituting <math>u_j-u_i</math> for <math>\delta_{ij}</math>, I now have four constraints.
 
:<math>
\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}
</math>
 
Or after some finagling:
 
:<math>
\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}
</math>
 
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 <math>2 \le n \le 4</math>.
 
Nevertheless, using the first constraint (arbitrarily), this makes the ILP:
 
{|class="wikitable"
|-
|align="center"|<math>\text{minimize}</math>
|{{NumBlk|:|<math>\sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij} \,</math>|{{EquationRef|1}}}}
|-
|rowspan="4" align="center"|<math>\text{subject to}</math>
|{{NumBlk|:|<math>\sum_{i=1}^n x_{ij} = 1 \quad \forall j \in 1 \ldots n \,</math>|{{EquationRef|2}}}}
|-
|{{NumBlk|:|<math>\sum_{j=1}^n x_{ij} = 1 \quad \forall i \in 1 \ldots n \,</math>|{{EquationRef|3}}}}
|-
|{{NumBlk|:|<math>u_i-u_1 - x_{i1} \le n-2 \quad \forall i \in 1 \ldots n  \,</math>|{{EquationRef|4}}}}
|-
|{{NumBlk|:|<math>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} \,</math>|{{EquationRef|5}}}}
|-
|rowspan="2" align="center"|<math>\text{and}</math>
|{{NumBlk|:|<math>0 \le x_{ij} \le 1 \quad x_{ij} \in \mathbb{Z} \,</math>|{{EquationRef|6}}}}
|-
|{{NumBlk|:|<math>u_i \ge 0 \,</math>|{{EquationRef|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.
 
{|class="wikitable"
|-
!If...
!One of must be true...
!Because...
|-
|<math>x_{ij}=1</math>
|<math>\delta_{ij}=1</math>
|We have traveled forward one city
|-
|<math>x_{ij}=0</math>
|<math>\delta_{ij} \ge 1-n</math>
|We have not traveled forward one city
|-
|}
 
(Its worth noting that we ignored the <math>\delta_{ij} \le n-1</math> 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...
 
{|class="wikitable"
|-
!colspan="2" rowspan="2"|
!<math>x_{ij}=1</math>
|-
!<math>\delta_{ij} = 1</math>
|-
!<math>x_{ij}=0</math>
!<math>\delta_{ij} \ge 1-n</math>
|<math>
\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}
</math>
|-
|}
 
Substituting <math>u_j-u_i</math> for <math>\delta_{ij}</math>, again just like last time...
 
:<math>u_i-u_j + nx_{ij} \le n-1</math>
 
...which is exactly the transcribed constraint, strongly suggesting that my suspicion was correct.  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 21:34, 6 September 2013 (UTC)
 
====Another idea====
 
I just had another idea to try and formulate the transcribed ILP.  What if we split the first city between index zero and index n, so that you can go from zero to one, and n-1 to n?  This could explain some of the mismatches in bounds we've seen too?  In other words: what if city 0 and city n are the same city, and you can only travel from city 0 and to city n?  I haven't verified it yet, but this will make the ILP something like:
 
{|class="wikitable"
|-
|align="center"|<math>\text{minimize}</math>
|{{NumBlk|:|<math>\sum_{i=0}^{n-1} \sum_{j=1}^n c_{ij}x_{ij} \,</math>|{{EquationRef|1}}}}
|-
|rowspan="3" align="center"|<math>\text{subject to}</math>
|{{NumBlk|:|<math>\sum_{i=0}^{n-1} x_{ij} = 1 \quad \forall j \in 1 \ldots n \,</math>|{{EquationRef|2}}}}
|-
|{{NumBlk|:|<math>\sum_{j=1}^n x_{ij} = 1 \quad \forall i \in 0 \ldots n-1 \,</math>|{{EquationRef|3}}}}
|-
|{{NumBlk|:|<math>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} \,</math>|{{EquationRef|4}}}}
|-
|rowspan="2" align="center"|<math>\text{and}</math>
|{{NumBlk|:|<math>0 \le x_{ij} \le 1 \quad x_{ij} \in \mathbb{Z} \,</math>|{{EquationRef|5}}}}
|-
|{{NumBlk|:|<math>u_i \ge 0 \,</math>|{{EquationRef|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.  [[Special:Contributions/151.190.254.108|151.190.254.108]] ([[User talk:151.190.254.108|talk]]) 13:56, 9 September 2013 (UTC)
 
:We have to avoid putting [[WP:OR|original research]] into the article.  [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 15:09, 9 September 2013 (UTC)
 
===Found the problem (I think)===
 
This appears to be the published version of Tucker's algorithm cited by Dantzig.  It's solving a significantly different version of the problem.
 
{{citation| last1=Miller | last2=Tucker | last3=Zemlin | first1=C. E. | first2=A. W. | first3=R. A.| title=
Integer Programming Formulation of Traveling Salesman Problems | journal=JACM | volume=7 | issue=4 | date=Oct. 1960 | pages=326&ndash;329 | doi=10.1145/321043.321046 | url=http://dl.acm.org/citation.cfm?id=321046 }}
 
From the problem statement: 
 
<blockquote>A salesman is required to visit each of <math>n</math> cities, indexed by <math>1, \ldots, n</math>. He leaves from a "base city" indexed by 0, visits each of the <math>n</math> other cities exactly once, and returns to city 0. '''During his travels he must return to 0 exactly <math>t</math> times''', including his final return (here <math>t</math> 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.  <small>''(emphasis added)''</small></blockquote>
 
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 <math>t</math> is fixed it is necessary to add the additional relation:
:<math>
\begin{array}{rl}
\sum_{i=1}^{n}x_{i0}=&t\\
\end{array}
</math>
 
Given this constraint I believe the formulation is correct for the problem it was designed to solve.  Setting <math>t=1</math> may solve the traditional TSP, but at this point I'm not willing to commit yes or no. 
 
[[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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''. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 22:50, 6 September 2013 (UTC)
 
===Where next on ILP?===
 
Nice catch&mdash;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?  [[User:Lesser Cartographies|Lesser Cartographies]] ([[User talk: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 <math>x_{ij}</math> are restricted to be integers in the interval
:::<math>
\begin{align}
0 \leq x_{ij} \leq 1 \\
\end{align}
</math>
::since sub-tours like those in Fig. 26-3-IV [omitted] also satisfy the conditions.  However, if so-called ''loop conditions'' like
:::<math>
\begin{align}
x_{12} + x_{23} + x_{31} \leq 2
\end{align}
</math>
::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. [[User:Duoduoduo|Duoduoduo]] ([[User talk: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. [[User:Duoduoduo|Duoduoduo]] ([[User talk:Duoduoduo|talk]]) 13:10, 8 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? [[Special:Contributions/70.167.155.42|70.167.155.42]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:53, 16 September 2013 (UTC)
 
== Ilya Gazman's solution ==
Please take a look at [http://stackoverflow.com/questions/19312677/java-traveling-salesman-found-polynomial-algorithm this], is it possible that this solution is really <math>O(n2^n)</math>?
:This is not the place to discuss unpublished results. n2^n is not polynomial. And if you think you have found a polynomial solution, [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm join the queue]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:50, 12 October 2013 (UTC)
 
== constraints on u_i needed, or helpful to state? ==
 
Isn't it necessary to state constraints on what the artificial variables u_i are?  I.e. something like 1 <= u_i <= n, for all i.  Or maybe it needs to be 2 <= u_i < n, or 0 <= u_i <= n-1.  The Integer Linear Programming Solution section currently reads:
<math>
\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} 
</math> 
 
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.

Latest revision as of 22:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML

E=mc2


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"