Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
mNo edit summary
No edit summary
Line 1: Line 1:
{{WikiProjectBannerShell|1=
{{WikiProjectBannerShell|1=
{{WikiProject Computer science |class=B |importance=top}}
{{WikiProject Environment|class=B|importance=High}}
{{maths rating|frequentlyviewed=yes|importance=Mid|field=discrete|class=B}}
{{WikiProject Economics|class=B|importance=Mid}}
{{Sys rating |class=B |importance=high |field=Operations research}}
{{WikiProject Futures studies |class=B |importance=mid}}
}}
}}
{{todo}}


== Example solution images ==
== Stacey Walked Hive Mind Doesn't Belong ==


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-->
This article is supposed to be about Malthusian catastrophe, and the following quote and reference certainly does NOT belong in the section where it has been placed:
: 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 ==
"In her book Humanity and it's foolishness, Stacey Walker invites readers to challenge previous views on individuality looking instead for a paradigm shift towards a collective Hive Mind. Once in Humanity has entered the 'Hive State' Walker postulates an end to resource depletion via the Druidic virtue of 'Survival of the Fittest'."
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)
: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 ==
That should be removed and if necessary placed into some sort of "related works" section.
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)


-- 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)
Addendum to note: I would also beg to differ with the statement implying that Druids are somehow responsible for the theory of 'Survival of the Fittest'.


== Princeton proof? ==
<span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/74.46.43.230|74.46.43.230]] ([[User talk:74.46.43.230|talk]]) 23:01, 29 June 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->


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,
==Exponential growth annual growth chart==
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".
It says next to this image "The annual increase graph does not appear as one would expect for exponential growth. For exponential growth, it should itself be an upward trending exponential curve whereas it has actually been trending downward since 1986. "  I don't think this is quite correct.  In an exponential growth situation, the annual growth rate (given in % like the graph), should remain constant, not trend upwards exponentially.  Comments? [[User:Edsanville|Ed Sanville]] 21:33, 22 April 2006 (UTC)
:This is because on 27 March, [[User:Casito|Casito]] edited the image file because "Excel Graphs look unprofessional", and changed it to percentage growth because it is "more useful", but didn't adjust the description; the original image, which you can still find [http://upload.wikimedia.org/wikipedia/en/archive/9/95/20060327181454%21World_population_increase_history.png here] showed absolute growth. Either the image should be converted back to absoute growth rate, or the description adjusted accordingly. For the time being I've adjusted the description to correct the inconsistency, but don't take that as a vote either way. (Worryingly, this image edit did not trigger my watchlists, even though that image was on my watchlist.) -- [[User:Securiger|Securiger]] 11:11, 24 April 2006 (UTC)


Colin M Davidson
I have completed the edits I planned to make to this page.  I would be interested to see any comments.


----
Buzz Bloom


:''How fast are the best known deterministic algorithms?''
Some of this article's information has been moved to ''[[Neanderthals Bandits and Farmers]]'' or ''[[Cannibals and Kings]]'' articles where it more rightfully belongs. The remainder contained some pretty basic errors (e.g. supply and demand) and has been mostly rewritten. I am pretty confident about this, but if you think it was correct we can discuss it here. [[User:H7asan]]


H7asan


----
We obviously have a disagreement regarding the relevance of "[[Beyond the Limits]]".
I found the entire book exactly on the point.  It deals with the exhaustion of food (and other resources) as a result of unconstrained population growth (as well as the unconstrained growth of consumption).  I definitely think this book should be referenced from a discussion of neo-Malthusean theory.  Why do you think otherwise?  Also, what is the proper mechanism for getting a disagreement of this kind resolved?


"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?"
By the way, I thought your moving of the discussion about the Harris and Tudge books to their own pages was a good idea.


Shouldn't it be "... that visits each city '''once''' ..."?
Buzz Bloom
: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.)
I have nothing against the ''Beyond the Limits'' book. (Actually I know nothing about it.) My problem was with the article which was empty. [[User:H7asan]]


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


== General Case ==
I plan to remove the two paragraphs beginning with "Another problem is that there is no strong evidence ... " including the two graphs.  This discussion is irrelevant to the topic of the Mathusuan catastrophe.  Malthus never described  population growth as being [[exponential]].  He said the growth would be expoential  in unchecked, and then only until a subsistance level was reached.  Growth of a population until a subsistance level would correspond to what Securiger describes in the current text I plan to remove as a Logistic curve.  All that the curves show is that the current trend of world population from 1950-2000 may be begining to reach a new limit of a kind that Malthus discusses: use of contraception, which Malthus called a vice.


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 put this notice of intent here to elicit comments or alternative suggestions before doing it.


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)
I also plan to edit the remaining material in the "Non-occurrence of the catastrophe" section cbecajuse I think it un fairly represents the state of the world at the end of the 19th century, which the anthropoligist [[Marvin Harris]] describes as one of approaching catastrophe as predicted by Malthus. The section should discuss the innovations of the twentieth century that offer opportunities to avoid the catastrophe, or only postpose it. From this perspective, I would change he title of the section to "Postponement or non-occurrence of the catastrophe".


====TSP with triangle inequality====
I also elicit comments or alternative suggestions regarding these intentions.


"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)
[[User:BuzzB]] Feb 28, 2004


This is easy to understand when we talk about points in some space like Euclidian or a sphere.
:I disagree with both proposed edits, quite strongly. Firstly, the paragraphs beginning "Another problem is..." are highly relevant. Malthus proposed a particular theory, which was essentially premised on three claims, one of them being the idea that a human population undergoes geometric growth if unchecked. Malthus' ''Essay'' has been disputed by many, and one major point of disputation - indeed one of the few points, pro- or anti-, that bothers to look at empirical facts - is that there is absolutely no evidence in support of this basic premise. It was pointed out as soon as the ''Essay'' was published, and continues to be pointed out today; if you like you can propose hypotheses to explain that fact away, but simply removing all evidence of it would severely bias the article.


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!!!
:Equally, we could point out that there is no evidence that food supply increases arithmetically, and that in fact it patently does not. One of the nicer summaries is this, written by Hazlitt in 1822:


I think something like this would be clearer to most readers:
::''All that is true of Mr Malthus's  doctrine then, is this, that the tendency of population to increase remains after the power of the earth to produce more food is gone; that the one is limited, the other unlimited. This is enough for the morality of the question: his mathematics are altogether spurious.''
"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.
:Secondly, you propose to edit the remaining material in that section, because you claim that it "un fairly represents the state of the world at the end of the 19th century, which the anthropoligist Marvin Harris describes as one of approaching catastrophe as predicted by Malthus". Huh? That section doesn't even discuss the end of the nineteenth century! If you meant "end of the '''18th''' century", which is mentioned, then of that time it says "At the time Malthus wrote, most societies had populations at or near their agricultural limits" - which is not contradicted by your point!? (Although there is plenty of evidence to believe that that statement is also somewhat exaggerated).


But I'm not sure if it's matematically right!
:I should point out that when I get time to do it justice, I plan to make extensive additions to this article, which in my opinion is currently very shallow and unencyclopedic. It currently represents the shallow, ill-defined, handwaving version of the Malthusian theory that is frequently dragged out in the pub or at dinner parties in support of some political argument or another. But in fact Malthus had a much more complete theory than is represented here, which was one of the seminal theories that gave rise to economics. (Although there is very little of the detail that is still widely accepted.) We need to work in its r&ocirc;le in the development of economics. Additionally the current article needs to mention Wallace, who had the idea first. Oh, and it also doesn't even mention the basic Malthusian idea that increased food supply automatically ''generated'' increased population until everyone was starving again, which segues into the r&ocirc;le the theory in had in justifying the oppression of the poor in nineteenth century politics - again from Hazlitt:
::''The instant, however, any increase in population, with or without an increase in the means of subsistence, is hinted, the disciples of Mr Malthus are struck with horror at the vice  and misery which must ensue to keep this double population down; nay, mention any improvement, any reform, any addition to the comforts or necessaries of life, any diminution of vice and misery, and the infallible result in their apprehensive imagination is only an incalculable increase of vice  and misery, from the increased means of subsistence, and increased population that would follow. They have but this one idea in their heads; it comes in at every turn, and nothing can drive it out.''
: [[User:Securiger|Securiger]] 11:28, 1 Mar 2004 (UTC)


: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 ==
I have extended the graph using the same data source, out to the years 1800-2005. Unfortunately, there seems to be some problem with the new image. Sometimes it appears when the article is displayed, and sometimes I see only a reference to an image. I have posted a query over at WikiMedia, and I hope to have it resolved in a day or two. Meanwhile, if you are looking for the image, please have some patience! --[[User:Aetheling|Aetheling]] 16:53, 30 September 2006 (UTC)


<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 colinearIf they are colinar then there's no difference between stopping at B and going directly from A to CThis 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)
Addressing the original question of this section, an exponential curve does not have a constant growth rate.  A constant growth rate yields a linear curve (for example, y=2x, a linear curve, has a growth rate of 2, a constant)An exponential curve has a growth rate that is, itself, an exponential curve (simplest example is y=e^x, a curve whose growth rate is equal to itself y'=e^x)For more information on this, you could visit the wikipedia page on [[exponential growth]].  I corrected the incorrect sentence.


== a proposed algorithm ==
Matt


How would this incremental algorithm work well (in terms of solution quality):
* You have misunderstood the meaning of the term "growth rate". When we say that a population of size X grows at a rate of 5%, for example, we mean that the growth this year will be 0.05X. If you solve the difference equation X(t+1)-X(t) = rX(t), the solution is exponential growth: X(t) = (1+r)^t X(0). I have therefore reverted your edit. —[[User:Aetheling|Aetheling]] ([[User talk:Aetheling|talk]]) 07:29, 12 February 2008 (UTC)


-start with tree looped cities
----


-for each new city:
I have updated the figures for world population and world population growth rate, to reflect the latest figures and estimates from the US Bureau of the Census. I also took the opportunity to improve these charts a little. I narrowed the range of the first and converted the vertical scale from semilog, so as to bring out more detail. If you look at this chart in its highest resolution, you can see that we have been following pretty closely the UN Medium projection (though it is still way too early to make any definitive judgement on this point). For the growth rate chart I added the latest projections by the US Bureau of the Census out to 2025, in red. Cheers! —[[User:Aetheling|Aetheling]] ([[User talk:Aetheling|talk]]) 18:16, 19 September 2008 (UTC).


--consider each existing edge
-------------


---get its current lenght
I wanted to point out that this approach to exponential growth is to limited. In the article it is suggested that you should view the population as different groups with different growth rates. You could compare a population that is decreasing with 2,5% per year with a population that consists of two groups. Lets say half of the population is a group that decreases with 10% and the other half increases with 5%. The latter would have a decrease of 2,5 percent in the first year. But this would slowly change over time. After 15 years you will see a growth of about three percent. And over time the growth of the entire population will be five percent. The group with the largest growth wins.


---get the total distance from the city being added to the edge's endpoints
This is an important aspect because people will respond differently to the changes in society. There are a lot of explanations why population growth slowes when gdp rises. There will be more contraceptives and more luxury etc. However there will be a group within the population that despite all these changes still has a preference for having children.
M. Meijer  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Meijer1973|Meijer1973]] ([[User talk:Meijer1973|talk]] • [[Special:Contributions/Meijer1973|contribs]]) 20:05, 29 August 2010 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->


---substract these two values
== Graph of World Population ==


--connect the city through the shortest detour
Hmm. I just wanted to object to a few things:
*The World Population graph is described as "''clearly... close to linear''". Really? To me it looks "clearly curved". (In fact, I think I see evidence of the [[logistic curve]], but that could well be spurious.) As alluded to in the article, 50 years is an awfully short time to get a good idea of how human population levels are changing. In fact, graphing the data from 1804-1999 given in the [http://www.geohive.com/global/linkg.php?xml=hist2&xsl=hist2 first external link] at that point in the article, would give a strong impression of ''exponential'' growth. Yes, maybe we're starting to see the beginning of the "slowing down" in growth that's predicted by the logistic model, but it's relatively early in that process, IMO, so I would be very hesitant to claim that the growth is no longer exponential &mdash; certainly not based on the data given here. ([[User:Dcljr|dcljr]], continued below)
** Yes, graphing the 6 points 1804-1999 does look ''closer'' to exponential (see below) - but the data prior to 1950 are extrapolations or approximations, based partly on the ''assumption'' of exponential growth prior to 1950 (and of course data after 2004 is purely extrapolated with some unstated model). Only the data highlighted in blue are based largely on actual census counts. (In any case, it looks closer still to two linear segments with an critical point near 1960). So the reason for concentrating on the last 50 years is because that is the sole period for which we have reasonably reliable data. And when you graph that real data, you get something that offers little support for the common assumption that "it's obviously exponential". Also it was not stated that it's "no longer exponential", but rather that there is no strong evidence that it ever has been. In fact it could be a very slow exponential, or maybe a very slow logistical, or perhaps linear, or quadratic - the point is we really don't know, and at any rate it certainly isn't a simple function. But at least the reason for choosing this period should be clarified. ([[User:Securiger|Securiger]])<br/>[[Image:Extrapolated world population history.png]]
*** Hmm... Part of the reason it might ''look'' closer to two linear segments is because the interpolating curve is (I assume) a cubic spline (and there's no point for it to go through between c. 1805 and 1925). Anyway, I agree with the rest of your paragraph. - [[User:Dcljr|dcljr]] 22:53, 7 Sep 2004 (UTC)


?
*Note that the plot of World Population Increase suggests that the rate of increase may actually still be going up, perhaps even (approximately) linearly (you always have to expect short-term fluctuations from the overall trend), which would imply '''quadratic''' growth. ([[User:Dcljr|dcljr]])
** How do you figure that? Apart from two years, it has been going down every year since 1987 - which is a third of the period for which we actually have reliable data! (Overall, there has been downturn in the growth rate for 26 of the 54 years considered.) ([[User:Securiger|Securiger]])
*The sentence that begins "''Also the rate of increase should increase, whereas, of the increase between [[1960]] and today, five-sixths occurred in the early [[1960s]]''", aside from being confusing, is '''completely misleading''', since a mere glance of the Increase graph shows something highly unusual happening in the years [[1957]]-[[1962]], resulting in a lcoal minimum in 1960! That dip in the graph is '''''the only reason''''' the statement above is true (to the extent that it is). ([[User:Dcljr|dcljr]])
**I'll try to rephrase the sentence you find confusing. The point is that in a positive exponential, the first [[difference equation|difference]] (and second difference, and all other differences) is also a positive, upward trending exponential. Thus when you get a true exponential growth curve and plot the differences between years, that rate-of-growth curve is itself an upward curving exponential. The rate-of-growth curve for human population clearly does not look like that at all.  This is seen even more so in the 2nd difference curve (below), which however I would not include on the main page because second differences are heavily affected by noise. If population was exponential, the second difference curve should also be exponential, in fact it has a lot of noise oscillating around zero but with an overall downward trend. As for the statement which you claim is "completely misleading", umm, your "objection" agrees almost exactly with the point and meaning of that sentence: if we were looking at exponential growth, most of the growth would be recent, but in fact most of the growth is due to "something highly unusual" happening back then - the big dip from '57 to '60, and also the huge surge from '60 to '63. And even if we interpolate the years '57 to '63 to remove this curious feature, 75% of the growth increase between 1950 and the peak year, 1990, occurred in the first half of that period. This is just not at all consistent with a positive exponential growth. It seems I need to make some clarifications on why this chart, and the data it represents, are wholly inconsistent with the implications of exponential growth. ([[User:Securiger|Securiger]])<br/>[[Image:Population 2nd derivative.png]]
***Maybe I misunderstood your purpose of pointing out the circa-1960 thing. I don't know. In any case, I wouldn't read much into the data of around that time. The "hiccup" might just be "noise" or might be due to a completely ''administrative'' cause (a change, say, in how censuses were taken or recorded in one or more large countries at the time &mdash; who knows?). I think most of our "differences" can be summed up by the following statement from the article: "''...short-term trends, even on the scale of decades or centuries, do not necessarily disprove the underlying mechanisms...''". I've been taking a much more long-term perspective, figuring that things like the 1960-ish "hiccup" and the "decrease in the increase" since 1986 are likely short-term deviations from the overall pattern over centuries (which is essentially unknowable anyway, but at least an exponential [and logistical] model has some theoretical basis). Anyway, I think both of us can agree that in the last 50 years or so the trend has not ''appeared to be'' exponential. On a completely different note, it would be interesting to consider (not in the article itself &mdash; or even here, necessarily) what role (tele)communications and transportation plays in all of this. Might population growth be "stabilizing" (''2nd derivative'' graph above) as a result of the increased interconnectedness of human populations? Perhaps that's the reason behind the "critical point" of around 1960? - [[User:Dcljr|dcljr]] 22:53, 7 Sep 2004 (UTC)


It is quadratic in terms of running time but how good solutions does it produce?
*Finally, I think the [[correlation coefficient]] is a pretty useless measure of anything in this context; someone should do an appropriate [[statistical test]] on the yearly data instead (I suggest an F-test to see whether an exponential term is needed over linear <nowiki>[intercept and slope]</nowiki> terms, and possibly an approximate lack of fit test). - [[User:Dcljr|dcljr]] 08:00, 6 Aug 2004 (UTC)
It always produces solutions with no crossings.
**Why do you think it is useless here? <math>r^2</math> is supposed to measure the fraction of the variability in y explained by the function of x - in this case, a linear model and exponential one explain the variability about equally well. I don't understand what you mean by "F-test to see whether an exponential term is needed over linear", but an F-test finds no significant difference in the residuals from linear and exponential models.  [[User:Securiger|Securiger]] 16:58, 7 Aug 2004 (UTC)
Another possibility might be to run the algorithm a few times with randomized order of the cities.
***Why is it useless? Because an exponential with slow growth can ''look'' linear and have a correlation close to 1! As for ''r''&sup2;, the article mentions the correlation coefficient not the coefficient of determination. Although obviously they're computationally the same in this case, the author was using it specifically to indicate linearity. In any case, even if you grant that "''practically'' speaking" the correlation is close to 1, consider what "practice" we're putting this information to: we're using these models to predict population levels far into the future (sometimes as far into the future as we have "reliable" data in the past, in fact &mdash; see above graph) and there can be a ''big'' difference between [[extrapolation]] using a linear model and one using an exponential. (Of course. That's why we're discussing this in the first place.) Oh, and I meant an ''ANOVA'' "F-test" for testing whether a coefficient in a regression model is zero (as opposed to an "F-test"  for testing the equality of two population variances). I should have been more specific. I'm not sure what "F-test" you did. - [[User:Dcljr|dcljr]] 22:53, 7 Sep 2004 (UTC)
[[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)
== Depletion of resources. ==


== Political Correctness ==
I think these things should be included because they strongly effect what decisions should be made regarding Malthusian theory.
I find it impossible to argue with or doubt the basic theory.  Almost the only requirements for its applicability are that life exists and there is no centralized control.
What is in question are the time scale and the nature of the catastrophe.  Both of these are strongly effected by pollution and resource depletion, especially energy and farm land.
One can consider food the "fuel" of non-industrial man, so energy is the modern equivalent.


Should this be Traveling Salesperson Problem? I seem to remember it being changed
The only way I feel I am being pessimistic is that nuclear (breader fission and/or fusion) power may well be able to replace fossil fuels with acceptable pollution and hazard, but no-one is sure of that.  Anyway it can't support the kind of increase in energy consumption we are seeing.


--[[User:143.53.132.154|143.53.132.154]] 10:56, 25 July 2006 (UTC)
David R. Ingham


: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.
== Citations Needed ==
--[[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.
There is no cite given for the following assertion:


== subexp time for euclidian TSP ? ==
''In fact, currently, food supply per person is several times higher than when Malthus wrote his essay''


Although the problem still remains NP-hard, it is known that there exists a subexponential time algorithm for it.  
Reference #10 links to the International Data Base home page, but does not contain a reference to any particular article.


Where can I find that algorithm ?
== Only showing to 1950 in the chart ==


I read what was discussed before, and I still think it is misleading to only show data from 1950-2000. Regardless of the precision of the data before 1950, the numbers can still be shown to be in the right ballpark. (One reader commented that the data before 1950 were often approxomations that, in part, assumed exponential growth - but one can not possibly assume linear growth, or there would have been no people before 1900! And the numbers for earlier dates are based on real data, not merely assumptions.)


* 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)
It's obvious that the period from 1950 to 2000 looks much more linear than, say, 1750 to 2000, and gives a misleading impression. The correct answer is, as has been said, that world population appears to follow a more complex function than simple linear, exponential, or quadratic growth. So why show only the select portion that appears linear? &ndash; [[User:Quadell|Quadell]] <sup>([[User_talk:Quadell|talk]])</sup> 13:47, 10 October 2005 (UTC)


== two questions on higher-dimensional TSPs ==
:Since there has been no discussion for 2 weeks on this, I'm going to change the article. &ndash; [[User:Quadell|Quadell]] <sup>([[User_talk:Quadell|talk]])</sup> 15:19, 23 October 2005 (UTC)


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?
== An Inaccurate Interpretation ==


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


*d(a,b) = 5
:"[Malthus] predicted that population growth would eventually outrun food supply,"
*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.
(this being one of many statements you've made in support of your interpretation) you seem to be claiming that Malthus was describing (and predicting) a future catastrophic global event - one that has yet to occur. That is not what he was saying, at all.


Again, do we need to use different approaches in solving TSPs of this type? --[[User:Ixfd64|Ixfd64]] 21:36, 10 November 2006 (UTC)
Malthus posited a doubling of world population every 25 years '''under ideal conditions''' (no shortage of food and none of the "positive" constraints of, for example, war and disease).  It is wrong to assume that Malthus actually thought the world population would double every 25 years until some future event in which there would not be enough food to sustain the population. (Given his ideal conditions and a population at the close of the 18th century of 1 billion, the world population would now be in excess of 250 billion.)  


* the triangle inequality is true in any number of dimensions. It is true for any metric space.
What he predicted was not some apocalyptic event but ''ongoing catastrophes'' playing out simultaneously in localized areas all over the world, wherever and whenever any group of people could not sustain themselves because their population had outrun the local area's food production capacity. His intent is quite clear in his statement (when discussing the American Indian):


== "Human performance" ==
:"Yet, [...] the effort towards population, even in this people, seems to be ''always'' greater than the means to support it." [emphasis added]


These works are so naive. If strip away the psychobabble,
It is also implicitly clear that when Darwin found in Malthus' essay the mechanism that drives evolution - a constant competition for survival due to limited resources - he didn't think Malthus was predicting some future global catastrophe.  
*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)
Malthus was addressing the idea of utopian societies gaining popularity at the time he wrote his essay. The point of his essay was to show that there could ''never'' be a population free from poverty and hunger and, therefore, the dream of a utopian society was just that - a dream. While your point that food production is now far greater than Malthus could ever imagine is true, what Malthus was saying remains valid. There are more people living in extreme poverty today than there were people (in total) at the time Malthus wrote his essay.


== What about the ants? ==
[[User:Paul Pomeroy|Paul Pomeroy]] 06:14, 24 December 2005 (UTC)


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? ==
I was going to make those very points (see above) about the logistic curve behaviour not contradicting Malthus's ideas, i.e. that he did not predict exponential growth but rather a tendency towards it, always modified by "checks", which is precisely where the logistics curve comes from. But then, why hasn't that change yet been made?


From "Computational Complexity" section:
I'd also like to draw attention to [Nassau Senior]'s work on wages, which has some of this thinking behind it. The particular point I want to bring out is his idea that machinery could theoretically compete with people for food, if only it needed fuel that drew on the same resources - which using more renewable fuels might soon cause. PML.


"Though see this work-in-progress attempt at a proof of polynomial time calculation for the 2-D undirected graph."
== Population, WHEN UNCHECKED, increases in a geometrical ratio ==


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)
Hi,


== Spelling==
when discussing the correctness of the geometric growth assumption and Malthus' theory in general it's important to keep Malthus' exact words in mind: ''"Population, WHEN UNCHECKED, increases in a geometrical ratio"''. Since the late 18th century occured plenty of Malthusian' checks to the human population: wars and epidemics, unhealthy living conditions, still existing infant mortality, contraception and abortion etc.


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)
Arguing that the Malthusian population model is void because we can't see a perfect exponential growth in the world population chart seems somewhat dubios; without considering the existence of checks (that, in Malthus' thinking, avoid, or delay, the "big catastrophe").


: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)
-- [[User:212.144.193.196|212.144.193.196]] 12:01, 19 February 2006 (UTC)


::One L as per Merriam-Webster. [http://mw1.merriam-webster.com/dictionary/travelling] --[[User:Thisisbossi|Thisisbossi]] 22:12, 8 February 2007 (UTC)
:user 212.144.193.196 is right on target. i wish she or he would get a name :) [[User:Anlace|Anlace]] 21:16, 23 June 2006 (UTC)
== Fertility Rate ==


::: 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)
There has been enormous decrease in female fertility worldwide and this is something that is not just specific to the west.  The average worldwide fertility is now 2.59 (2.1 is the replacement rate fertility at which no population growth will occur in the long term).  For instance the fertility rate in India is now 2.73. This implies that growth is not exponential since a constant fertility rate would be required for exponential growth. This is the reason for the UN estimates. A scientific approach (scientific does not mean environmentalist) implies that population growth must level off due to decreasing fertility.  Therefore neo-malthusian theory makes no sense and has just been debunked. QED bitches.


::::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 AmericanMy 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 modifiedI 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)
:the anonymous author above makes little sense.  the birth rate of India for example would lead to tens of millions more people in that country in the next decades if the rate is left unchecked and death rates do not escalate severelymoreover there are many ways population growth can "level off" besides decreased fertilitythus the author above has revealed his or her inherent lack of scientific approach. [[User:Anlace|Anlace]] 04:39, 2 July 2006 (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)
:I'm not sure what the commenter means by 'female fertility'. There is no reason to think that women are physiologically less fertile than they used to be.  The reduction in actual birth rates is due mainly to contraception, abortion, and to the increasing economic independence of women, which means they do not need to marry as soon as possible.  I don't know about 'neo-Malthusian theory', but Malthus himself was aware of the primitive methods of birth control available in his day, and deplored them as immoral 'violations of the marriage bed'. His own preferred method of birth control was 'moral restraint', i.e. abstention from marriage by those who cannot afford to raise children, combined with chastity by the unmarried.  Which is a bit grim, but don't forget he was a clergyman.[[Special:Contributions/109.158.128.2|109.158.128.2]] ([[User talk:109.158.128.2|talk]]) 13:33, 20 January 2014 (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.
That assumes fertility does not continue to decrease and we have no reason to expect that will happen given that it has decreased from 6 to less that 3 worldwide from 1960 to 1990. You say India will continue to experience population increase. It will but at a slower rate which is completely inconsistent with Malthus. Showing an increase in population is not enough. You are required to show an exponential increaseA decrease from 6 to 3 definitely implies that growth is not exponential since exponential growth requires constant fertility.
[[User:Psy wombats|Psy wombats]] 14:46, 23 October 2007 (UTC)


== Political Correctness ==
:Could we please have a moratorium on comments about Malthus by people who have never read him?  Malthus never claimed that population actually increases at an exponential rate, only that it would do if there were no 'checks' on reproduction.  He then devoted hundreds of pages (in the later editions of his Essay) to analyzing what those 'checks' were.[[Special:Contributions/109.158.128.2|109.158.128.2]] ([[User talk:109.158.128.2|talk]]) 13:37, 20 January 2014 (UTC)


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 -->
::i think someone is missing the big picture here. have you seen the "low" projections for india and many lesser developed countries (i am not considering India lesser developed by the way).  the real issue is carrying capacity. do you honestly believe there is carrying capacity for these burgeoning billions when over one billion people today do not have safe drinking water?  this is not a simple matter of sharing the wealth.  we are simply living on a finite planet, whose resources are stretched thinly.  wake up and smell the coffee. the catatastrophe is occurring now. by the way your credibility would grow exponentially if you would create an account :) [[User:Anlace|Anlace]] 05:15, 2 July 2006 (UTC)
::: Carrying capacity is a variable in the [[Logistic curve]], it is not part of malthus' original theory afaik. [[User:Kim Bruning|Kim Bruning]] 09:07, 20 July 2006 (UTC)


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-->
== Logistic curve and lotka-volterra ==
They're already mentioned, but not emphasized. Could we maybe stress that there are currently improved population models available. Both these newer models *do* actually have malthusian style exponential growth for certain parameters. They just also have different behaviour under other parameters. --[[User:Kim Bruning|Kim Bruning]] 09:01, 20 July 2006 (UTC)


== Nearest Neighbour Algorithm cannot find worst possible solution. ==
==NPOV & Factual accuracy==
The section on "is the catastrophe happening?" seems to have a Non-NPOV and perhaps even some factual accuracy.  I just stumbled on this article and don't know enough to necessarily correct it all myself, but tagged the section.  For example, the unsourced and original opinion that the UN study is "less scientific" than contradicting studies.  There are weasel words/phrases like "numerous scholars accept...", "some analysts consider...", etc.  I think the section has definitely been massaged to push a subtly apocalyptic point of view.--[[User:160.39.213.64|160.39.213.64]] 01:54, 27 September 2006 (UTC)


I changed the text that said the nearest neighbour algorithm can find the worst possible solution and removed the asociated request for citation.
I did enjoy the bit about one lone economist suggessting that global starvation might not be inevitable! Most economists (and others with a half a brain!) regard theories of Malthusian catastophes as a 19th century goof, and comprehensively disproven! Neo-Malthusianism is up there with those who believe that reading the Bible backwards reveals Satanic messages! --[[User:Nmcmurdo|Nmcmurdo]] 19:02, 23 October 2006 (UTC)


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.
I agree that the earlier version had some serious problems with bias. As time permits, I have been trying to improve this section with both text and figures that let readers make up their own minds based on the most impartial and accurate graphics that I can devise. — [[User:Aetheling|Aetheling]] 20:55, 24 October 2006 (UTC)


E.......C.AB...D........
As first user states. There are lots of NPOV issues with that section. Whoever authored that section was determined to reject all notions that the Malthusian Catastrophe is shoved back/not happening at all. Then again murdo, isn't it a bit personal to talk, ad hominem, to the Neo-Malthusians?
We sure could use a little tact everywhere in Wikipedia. [[User:Pasonia|Pasonia]] 03:31, 18 November 2006 (UTC)


The nearest neighbour solution A->B->-C->D->E takes 1+3+7+15=26.
True.  The way I heard it, the world food supply is more than enough to comfortably sustain the entire population, and famine is due mostly to politics and poor distribution. [[User:Vultur|Vultur]] 9:48 PM, 16 December 2006 (UTC)


An alternate solution A->E->B->C->D is 10+11+3+7 = 31.
:there is no question that more sourcing is needed on this article (along with 99 percent of all wikipedia articles}.  Vultur, the way you "heard it" is factually in error.  the world food supply is presently being produced by un[[sustainable]] agricultural methods. in some of the biggest production areas (eg great plains of USA and north China plain) groundwater is being exhausted.  there are countless other factual examples of the fact that food production is not foreseeably adequate...let alone adequate [[drinking water]].  thus i hope the zeal expressed above will translate into acquiring fact based sources. regards. [[User:Anlace|Anlace]] 15:31, 17 December 2006 (UTC)


There is a worse solution than the worst possible NN solution.  Therefore NN cannot result in the worst possible solution.
== Malthusian catastrophe in popular culture ==


All that said, maths is not my strongest point, so please point out if there's a flaw in my positionThanks.
Maybe this article is asking for a "Malthusian catastrophe in popular culture" section, as popular on many other articles?  To seed such a section, here's a piece of trivia: the [[Guardians of the Universe]], from DC Comics, originated in a planed named Maltus, and were called Maltusians.  Some of them evolved into the Guardians and left for Oa, while most stayed behind, and were later depicted as much less advanced than Earth, presumably due to Malthusian effects.  It may be that the name is only a coincidence, and as such I'd rather not touch the article, but I believe it's intentionalI'm sure other people can remember lots of other pop references. [[User:LaloMartins|LaloMartins]] 05:01, 12 October 2006 (UTC)


--irrevenant [ [[User_Talk:Irrevenant|talk]] ] 03:15, 17 March 2007 (UTC)
== Critics of Malthusian catastrophe ==


Following are the sections I wrote on critics of malthusian catastrophe. However, they might first be further discussed before any display on the article page again, so I moved them here. Please state if you find them reasonable or not. [[User:Mortsggah|Mikael Häggström]] 06:54, 9 June 2007 (UTC)


== Probability question ==
===Economically===
By the simple rule of supply and demand, an increasing population would lead to an increasing demand for food. If then the supply of food isn't increasing at the same rate, the price of food will increase. Thus, more people would find it worth to work agricultural, and if the land area of agriculture isn't enough, find alternatives for producing food. Such alternatives could be food based on [[algae]] or [[fungi]] <ref>www.ias.ac.in/resonance/May2004/pdf/May2004p33-40.pdf</ref> or, on the long term, purely [[synthetic food]].
On the other hand, increasing prices of food would render the consumers to find cheaper alternatives. Thus, the worst catastrophe that could happen is that all people would have to become vegetarians, instead of the wasting system of eating animals eating vegetables. Alternatively, the population would have to eat more algae or seaweed.


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)
:The problem is that you run into limits of what can physically be produced.  Prolonged exponential growth would lead to absurdities like having more people than there are atoms in the universe, or a vast ball of humans expanding into space faster than the speed of light.  Supply and demand isn't going to make those scenarios any less absurd.  Even to get remotely close to those scenarios would require sci-fi-style technology (think [[Ringworld]]), which, while it may appear in the future, should not be taken for granted.  Currently feasible things like eating seaweed would buy us a few doubling times, at best, and the population doubles every 70 years at a modest 1% growth rate. 


:Consider simulating to get an idea. It seems it should probably be exponentially small.[[User:Ninjagecko|Ninjagecko]] 12:38, 8 May 2007 (UTC)
:Malthus agreed with you that agricultural output could be increased, but he didn't believe it could increase as fast as a growing population.[[User:Rsheridan6|Rsheridan6]] 03:25, 15 June 2007 (UTC)


== Plagiarism? ==
Shouldn't the growing occurrence of obesity in the developing world render Malthus' theory (at least as it relates to food) void once and for all? I mean now we can manufacture junk food with ridiculously high calorie content for next to nothing. The number of obese individuals worldwide has now equalled the number of underfed.  This should be mentioned somewhere http://www.fao.org/FOCUS/E/obesity/obes1.htm[[User:81.153.62.232|81.153.62.232]] 20:23, 10 July 2007 (UTC)


Compare:
:That has nothing to do with the essence of the theory.  Read the paragraph above yours:  where is the cheap junk food going to come from when there are 12, 24, 48, 96, or 192 billion people?  The theory is based on the fundamental nature of food production and population growth, and the fact that farming productivity outstripped population growth for a century or two (really not a long time on an evolutionary or historical scale) doesn't render the theory null and void forever, any more than the fact that oil production increased for a few centuries proves that there's an infinite supply of oil in the ground.  To render it void forever, you would have to either show that we can reliably have food production increases similar to the green revolution on a regular basis, or that population growth will cease forever. [[User:Rsheridan6|Rsheridan6]] 05:53, 11 July 2007 (UTC)


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)"
===Distribution===
The starvation we see on earth today isn't a result of an insufficiency of the earth to supply food, even without prospects of purely [[synthetic food]] and a shift to eating algae and fungi. Rather, it's a result of inability to transport it to all areas where it is needed.
By the [[Malthusian catastrophe#economically|economic reasons]] above, this will continue into the future as well. Thus, there will be no deterioration of mankind due to the Malthusian catastrophe, although an unfair distribution of supply might persist.


with http://www.tsp.gatech.edu/history/index.html
:The sections (Distribution in particular) are stating opinion as fact, and not crediting the opinion to any source. [[Wikipedia:No original research#Primary, secondary, and tertiary sources|Wikipedia is a tertiary source]], and must also be written from a [[WP:NPOV|neutral point of view]]. We cannot say "it's obvious that this theory is wrong because blah", we must say "John F. Doe and Dr. Foo disagree with this theory due to blah". [[User:Capi|Capi]] 14:55, 14 June 2007 (UTC)


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.
::Yeah, right. [http://ipsnews.net/news.asp?idnews=38372] Guess the U.N. know what they are talking about when they say that there's already enough food for 12 billion people. And the population is expected to reach a maximum of 9 billion. Actually in many parts of the world the population already stopped growing. So I don't think figuring out how to grow stuff in space is our primary problem to stop people starving and I also don't think the Malthusian catastrophe is about to happen any time soon. --[[User:Mudd1|Mudd1]] 13:44, 25 August 2007 (UTC)


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 -->
== Load of clap-trap ==


: 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)
What a load of clap-trap!  Even Malthus agreed that since his predicted catastrophe never happened, he was wrong.  Would that his modern-day supporters were as intelligent and honest as he.  


== Problems with "Example letting the inversion operator find a good solution" section ==
==Man does not live by bread alone==


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 most discussions/articles RE: the sustaniability or otherwise of future (or even current) population levels there is far too much emphisis on the feasibility (or otherwise) of meeting projected demands of FOOD but what of other resources required by modern people to lead worthwhile lives like housing, clean water, clothing, energy, transport, medicine and all manner of manufactured goods. There are serious question marks over the long term availability of sufficent supplies of raw materials to meet these needs even at current population levels. And what pollution ? All other considerations being equal surely twelve billion people will produce a lot more than say two billion. [[User:80.229.222.48|80.229.222.48]] 11:14, 11 August 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)
==Population growth==


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)
http:Disablelink//www.optimumpopulation.org/ your right about this one... it is a spam one really here ... because of the donation thing pov. etc... thanks for catching that NJGW it is not a good link here at all... and I guess you agree that you probably mistakenly removed this one previously... that is excellent information ''M. King Hubbert on the Nature of Growth. 1974'' Thanks for being alert on the other one. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 18:46, 5 September 2008 (UTC)
:The Hubbert link doesn't really belong either... it doesn't mention Malthus or speak of population drops due to catastrophe. It deals with population growth.  I think other editors should look very closely at that link and consider removing it.  It has also been inserted into other articles recently to which it is only tangentially related.  [[User:NJGW|NJGW]] ([[User talk:NJGW|talk]]) 07:33, 6 September 2008 (UTC)
::Sorry I think you are wrong. It is all about exponential growth and use of resources .. and future consequences.. Why would it have to mention Malthus to be pertinent? It goes way beyond Malthus... Malthus would have swooned over Hubberts charts and graphs. Hubbert was probably was the most well known Geo-scientist produced by the U.S. -- Removing that link ... is removing very good information. Not suggested. Look at Hubberts exponential growth explanation in the article. For that reason alone it is good... also here is a sample from the paper in question:
::''Yet, during the last two centuries of unbroken industrial growth we have evolved what amounts to an exponential-growth culture. Our institutions, our legal system, our financial system, and our most cherished folkways and beliefs are all based upon the premise of continuing growth. Since physical and biological constraints make it impossible to continue such rates of growth indefinitely, it is inevitable that with the slowing down in the rates of physical growth cultural adjustments must be made.''[http://www.technocracy.org/natureofgrowth.htm] Now that is purely Malthusian. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 15:40, 6 September 2008 (UTC)
:::Malthusian? Perhaps (though it's your word against Hubbert's lack of using the name Malthus for now), but how is it related to Malthusian catastrophes?  Lots of folks have written works which may be traced back in some way to Malthus, but we shouldn't list every one of those papers here, or even at Malthus' article for that matter.  The external links should be a stand-out resource which speaks about the topic itself, or else we'll have every single person who likes a tangentially related website wanting to link it here. 


== Reference to MATLAB ==
:::Better idea: try finding a way to use it as a ref here or at Malthus in a way which doesn't violate [[wp:OR]][[User:NJGW|NJGW]] ([[User talk:NJGW|talk]]) 19:18, 6 September 2008 (UTC)
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 ==
::::E.T's are supposed to expand the information not directly in the article but pertinent.
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)
::::''Wikipedia does not publish original research or original thought. This includes unpublished facts, arguments, speculation, and ideas; and any unpublished analysis or synthesis of published material that serves to advance a position. This means that Wikipedia is not the place to publish your own opinions, experiences, or arguments.''
:I rewrote and moved this section. [[User:Dcoetzee|Dcoetzee]] 23:02, 7 August 2007 (UTC)


==Contested move request==
::::How it is you interpret that file as such is not known. This is a scientist who was called before a subcommittee of the Congress to testify about energy, as it relates the environment and consequences of lack of energy in the future. Energy is what supports our system. If you loose access to it the system stops. Original research? Hubbert was called before these politicians to try and explain a very Malthusian problem... We use petrol also for making fertilizer and pesticides... That is the [[green revolution]]... or what powers it. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 20:56, 6 September 2008 (UTC)
<!--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? ==
:::::I think you mean ELs, not ETs.  In any case, you should read [[wp:EL]], and especially [[wp:ELYES|the list of suggested external links]] and the thirteenth entry in [[wp:ELNO|the list of links to avoid]] (which reads in part "Sites that are only indirectly related to the article's subject: the link should be directly related to the subject of the article").  The article is not about Malthusian catastrophies, Malthus and catastrophies are not mentioned, and besides your interpretation we have no indication that this was essay was written to "explain a very Malthusian problem".  I'm not trying to be mean, and I see why you believe what you believe (and even agree with your main points regarding Hubbert peaks and population growth), but that doesn't make it appropriate to link this essay in this and other tangentially related articles.  Besides, it exists appropriately as a link in at least 6 other articles already.  [[User:NJGW|NJGW]] ([[User talk:NJGW|talk]]) 21:36, 6 September 2008 (UTC)


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)
I agree with NJGW here. The [[WP:OR]] violation he is referring to is not in the contents of the linked article itself; it's in your tacit assumption that the latter relates to the main topic of Malthusian Catastrophe. That is far from being a given. I echo his guidance in trying to place it within the body of the article. It's compliance or lack thereof will then become apparent. ~ [[User:Alcmaeonid|Alcmaeonid]] ([[User talk:Alcmaeonid|talk]]) 22:06, 6 September 2008 (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 ==
::Ok... but I do not agree... [[peak oil]] is about Malthusian as it gets, in every sense. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 05:25, 7 September 2008 (UTC)
:::I think it's more accurate to say that some of the predictions of [[oil depletion]] resemble Malthusian catastrophes, but that's already covered [[Malthusian_catastrophe#Application_to_energy.2Fresource_consumption|here]] and a link to Peak oil exists in the see also section.  I see no reason to violate wp:ELNO-13 in this case.  [[User:NJGW|NJGW]] ([[User talk:NJGW|talk]]) 15:09, 7 September 2008 (UTC)
::::You have a point there. Bartlett does a good job explaining things. I am thinking now that I agree with your points in general, after looking more into the issues you discussed. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 22:33, 8 September 2008 (UTC)


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)
== Anarcho-primitivism connection? ==


== Question:"It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem" ==
First I just want to point out that links within the See also section shouldn't have the same level of scrutiny as those in the EL sections.  That said, this connection is a bit loose... I can see how one might argue that an Anarcho-primitivist might support the return to a different lifestyle in order to ''avoid'' a Malthusian catastrophy, but couldn't the same be said for any type of primitivst?  Maybe a section could be inserted in the text which discusses movements which aim to mitigate a catastrophy and primitivism could be mentioned there (but since this is essentially a population issue, a sudden drop in technology levels worldwide would create an instant and artificial--rather than organic--Malthusian catastrophy).


Is there any proof or analysis about this? Thanks.[[User:Ifcongif|Ifcongif]] ([[User talk:Ifcongif|talk]]) 01:57, 11 November 2008 (UTC)
This seems a bit tricky, but if done correctly could improve the article. [[User:NJGW|NJGW]] ([[User talk:NJGW|talk]]) 18:11, 18 September 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? ==
It's complicated to distinguish "artificial" from "organic" social phenomenon. The connection is very clear if you consider that the "Malthusian catastrophe" is in itself part of the anarcho-primitivist theory on why civilization is unsustainable. In this sense, the anarcho-primitivists are not exactly looking to “mitigate” the problem, but to find alternatives of sustainable survival trough the inevitable collapse. [[User:Maziotis|Maziotis]] ([[User talk:Maziotis|talk]]) 21:05, 18 September 2008 (UTC)


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)
:[[Anarcho-primitivism]] is an [[Anarchism|anarchist]] critique of the origins and progress of [[civilization]]. According to anarcho-primitivism, the shift from [[hunter-gatherer]] to [[Agriculture|agricultural]] subsistence gave rise to [[Social_stratification#Non-stratified_societies|social stratification]], [[coercion]], and [[Social alienation|alienation]]. Anarcho-primitivists advocate a return to non-"civilized" ways of life through [[Industrialisation|deindustrialisation]], abolition of [[division of labour]] or [[specialization (functional)|specialization]], and abandonment of [[technology]]. There are  other non-anarchist forms of [[primitivism]], and not all primitivists point to the same phenomenon as the source of modern, civilized problems. I fail to see how this is related... much to Malthus, if at all. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 02:10, 19 September 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)


::Maybe you should try to read more than the first paragraph of an article in wikipedia when trying to understand a subject. [[User:Maziotis|Maziotis]] ([[User talk:Maziotis|talk]]) 09:32, 19 September 2008 (UTC)


Thank you very much.[[User:Ifcongif|Ifcongif]] ([[User talk:Ifcongif|talk]]) 02:07, 18 November 2008 (UTC)
I believe there is not exactly a Marx in anarcho-primitivism like there is one in marxism. There is this general assumption that civilization is a two second disease in our biological history. Other than that, there is a space for different interpretations to what the unsustainability of civilization means. I never meant to argue that the Malthusian theory is a corner stone in anarcho-primitivist theory. Simply, if I understood it well, this theory is an explanation on how agriculture is unsustainable for human beings in the long run. This in turn is central to a political philosophy called anarcho-primitivism. There is where I see a clear connection. [[User:Maziotis|Maziotis]] ([[User talk:Maziotis|talk]]) 11:52, 19 September 2008 (UTC)


== Software? ==
::Yeah probably that is the angle that would have to be tried to get at... if a link were to be made. As NJGW said ''Maybe a section could be inserted in the text which discusses movements which aim to mitigate a catastrophy and primitivism could be mentioned there (but since this is essentially a population issue, a sudden drop in technology levels worldwide would create an instant and artificial--rather than organic--Malthusian catastrophy).''... Another section might list a bunch of alternative concepts... but still Anarcho-primitivism being in my opinion... a kind of political social movement... that is possibly a couple of steps from even mainstream hetorodox thinking, although I am familiar with Tainter and his ideas, and also some of the other well known advocates of this movement. [[User:Skipsievert|skip sievert]] ([[User talk:Skipsievert|talk]]) 14:25, 19 September 2008 (UTC)


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)
== does not belong in lede ==


== Translation from DE ==
"An August 2007 science review in The New York Times raised the claim that the Industrial Revolution had enabled the modern world to break out of the Malthusian Trap,[1] " ... uh... the idea the that the Industrial Revolution enabled the modern world to break out of the Malthusian Trap goes back to ... well, shortly after Malthus. Certainly it was widely accepted among economists by the early 20th century. And that's way, way, way before 2007. This is so outdated (2007 vs. 1900) and trite ("raised the claim" to characterize a widely held view completely supported by empirical evidence) that it just does not belong in the article, and definitely not in the lede.[[User:Radeksz|radek]] ([[User talk:Radeksz|talk]]) 22:23, 1 August 2009 (UTC)


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 am curious if Malthusian theory can be applied to other areas of growth. For example, educational institutions continually birthing graduates in relation to the number of jobs availableIn trying to ease the problem, different organizations or government entities are wanting to create new jobs. This is not stated as reality but to only an example.  
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>
[[User:Beetlebailey75|Beetlebailey75]] ([[User talk:Beetlebailey75|talk]]) 09:01, 3 April 2010 (UTC)beetlebailey75
''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)
== This sentence is questionable ==
: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 ==
"In some cases, population growth occurs due to increasing life expectancies, even though fertility rates are below replacement."
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? ==
Does not seem to make mathematical sense. The mechanism where increasing life expectancies creates population growth works in the way that: greater life expectancies cause increasing fertility rates, which causes population growth. Increasing life expectancies cannot create population growth without increasing fertility rates about replacement first. Think about the arithmetic of it:


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:
If you have an initial number, say, 0, and can (only) add or subtract as many 1s from it anytime, you need to add more times than you subtract to get a greater number. I'm no mathematician, by the way, so I don't know if this is always true, but I'm pretty true it applies here. Anyways, if "fertility rates are below replacement," as in the sentence in question, it corresponds to subtracting more times than adding, if the resulting number corresponds to the population, but since you need to add more times than you subtract to get a greater number, the population could only decrease. If the population could only decrease, it wouldn't make sense how "population growth occurs". If no one objects, I'll remove this statement at February. [[Special:Contributions/173.180.202.22|173.180.202.22]] ([[User talk:173.180.202.22|talk]]) 06:36, 2 January 2012 (UTC)
<math>
:And also, the example where there's "1.3 children/woman" doesn't seem to be a replacement rate because the children's parents don't necessarily have to be replaced. [[Special:Contributions/173.180.202.22|173.180.202.22]] ([[User talk:173.180.202.22|talk]]) 07:10, 2 January 2012 (UTC)
\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.
== Rename ==


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.
Wouldn't it be better to have this article, with a slight rewrite and shift of focus, under [[Malthusian theory]] (currently a redirect here) rather than "catastrophe"? The way the idea works is that there are demographic checks on income per capita but a "catastrophe" in the sense of something sudden and very bad is not necessarily a consequence of the model.[[User:Volunteer Marek|<font color="Orange">Volunteer</font><font color="Blue">Marek</font>]] 08:13, 4 July 2012 (UTC)

Revision as of 15:36, 24 August 2014

Template:WikiProjectBannerShell

Stacey Walked Hive Mind Doesn't Belong

This article is supposed to be about Malthusian catastrophe, and the following quote and reference certainly does NOT belong in the section where it has been placed:

"In her book Humanity and it's foolishness, Stacey Walker invites readers to challenge previous views on individuality looking instead for a paradigm shift towards a collective Hive Mind. Once in Humanity has entered the 'Hive State' Walker postulates an end to resource depletion via the Druidic virtue of 'Survival of the Fittest'."

That should be removed and if necessary placed into some sort of "related works" section.

Addendum to note: I would also beg to differ with the statement implying that Druids are somehow responsible for the theory of 'Survival of the Fittest'.

—Preceding unsigned comment added by 74.46.43.230 (talk) 23:01, 29 June 2009 (UTC)

Exponential growth annual growth chart

It says next to this image "The annual increase graph does not appear as one would expect for exponential growth. For exponential growth, it should itself be an upward trending exponential curve whereas it has actually been trending downward since 1986. " I don't think this is quite correct. In an exponential growth situation, the annual growth rate (given in % like the graph), should remain constant, not trend upwards exponentially. Comments? Ed Sanville 21:33, 22 April 2006 (UTC)

This is because on 27 March, Casito edited the image file because "Excel Graphs look unprofessional", and changed it to percentage growth because it is "more useful", but didn't adjust the description; the original image, which you can still find here showed absolute growth. Either the image should be converted back to absoute growth rate, or the description adjusted accordingly. For the time being I've adjusted the description to correct the inconsistency, but don't take that as a vote either way. (Worryingly, this image edit did not trigger my watchlists, even though that image was on my watchlist.) -- Securiger 11:11, 24 April 2006 (UTC)

I have completed the edits I planned to make to this page. I would be interested to see any comments.

Buzz Bloom

Some of this article's information has been moved to Neanderthals Bandits and Farmers or Cannibals and Kings articles where it more rightfully belongs. The remainder contained some pretty basic errors (e.g. supply and demand) and has been mostly rewritten. I am pretty confident about this, but if you think it was correct we can discuss it here. User:H7asan

H7asan

We obviously have a disagreement regarding the relevance of "Beyond the Limits". I found the entire book exactly on the point. It deals with the exhaustion of food (and other resources) as a result of unconstrained population growth (as well as the unconstrained growth of consumption). I definitely think this book should be referenced from a discussion of neo-Malthusean theory. Why do you think otherwise? Also, what is the proper mechanism for getting a disagreement of this kind resolved?

By the way, I thought your moving of the discussion about the Harris and Tudge books to their own pages was a good idea.

Buzz Bloom


I have nothing against the Beyond the Limits book. (Actually I know nothing about it.) My problem was with the article which was empty. User:H7asan


I plan to remove the two paragraphs beginning with "Another problem is that there is no strong evidence ... " including the two graphs. This discussion is irrelevant to the topic of the Mathusuan catastrophe. Malthus never described population growth as being exponential. He said the growth would be expoential in unchecked, and then only until a subsistance level was reached. Growth of a population until a subsistance level would correspond to what Securiger describes in the current text I plan to remove as a Logistic curve. All that the curves show is that the current trend of world population from 1950-2000 may be begining to reach a new limit of a kind that Malthus discusses: use of contraception, which Malthus called a vice.

I put this notice of intent here to elicit comments or alternative suggestions before doing it.

I also plan to edit the remaining material in the "Non-occurrence of the catastrophe" section cbecajuse I think it un fairly represents the state of the world at the end of the 19th century, which the anthropoligist Marvin Harris describes as one of approaching catastrophe as predicted by Malthus. The section should discuss the innovations of the twentieth century that offer opportunities to avoid the catastrophe, or only postpose it. From this perspective, I would change he title of the section to "Postponement or non-occurrence of the catastrophe".

I also elicit comments or alternative suggestions regarding these intentions.

User:BuzzB Feb 28, 2004

I disagree with both proposed edits, quite strongly. Firstly, the paragraphs beginning "Another problem is..." are highly relevant. Malthus proposed a particular theory, which was essentially premised on three claims, one of them being the idea that a human population undergoes geometric growth if unchecked. Malthus' Essay has been disputed by many, and one major point of disputation - indeed one of the few points, pro- or anti-, that bothers to look at empirical facts - is that there is absolutely no evidence in support of this basic premise. It was pointed out as soon as the Essay was published, and continues to be pointed out today; if you like you can propose hypotheses to explain that fact away, but simply removing all evidence of it would severely bias the article.
Equally, we could point out that there is no evidence that food supply increases arithmetically, and that in fact it patently does not. One of the nicer summaries is this, written by Hazlitt in 1822:
All that is true of Mr Malthus's doctrine then, is this, that the tendency of population to increase remains after the power of the earth to produce more food is gone; that the one is limited, the other unlimited. This is enough for the morality of the question: his mathematics are altogether spurious.
Secondly, you propose to edit the remaining material in that section, because you claim that it "un fairly represents the state of the world at the end of the 19th century, which the anthropoligist Marvin Harris describes as one of approaching catastrophe as predicted by Malthus". Huh? That section doesn't even discuss the end of the nineteenth century! If you meant "end of the 18th century", which is mentioned, then of that time it says "At the time Malthus wrote, most societies had populations at or near their agricultural limits" - which is not contradicted by your point!? (Although there is plenty of evidence to believe that that statement is also somewhat exaggerated).
I should point out that when I get time to do it justice, I plan to make extensive additions to this article, which in my opinion is currently very shallow and unencyclopedic. It currently represents the shallow, ill-defined, handwaving version of the Malthusian theory that is frequently dragged out in the pub or at dinner parties in support of some political argument or another. But in fact Malthus had a much more complete theory than is represented here, which was one of the seminal theories that gave rise to economics. (Although there is very little of the detail that is still widely accepted.) We need to work in its rôle in the development of economics. Additionally the current article needs to mention Wallace, who had the idea first. Oh, and it also doesn't even mention the basic Malthusian idea that increased food supply automatically generated increased population until everyone was starving again, which segues into the rôle the theory in had in justifying the oppression of the poor in nineteenth century politics - again from Hazlitt:
The instant, however, any increase in population, with or without an increase in the means of subsistence, is hinted, the disciples of Mr Malthus are struck with horror at the vice and misery which must ensue to keep this double population down; nay, mention any improvement, any reform, any addition to the comforts or necessaries of life, any diminution of vice and misery, and the infallible result in their apprehensive imagination is only an incalculable increase of vice and misery, from the increased means of subsistence, and increased population that would follow. They have but this one idea in their heads; it comes in at every turn, and nothing can drive it out.
Securiger 11:28, 1 Mar 2004 (UTC)

I have extended the graph using the same data source, out to the years 1800-2005. Unfortunately, there seems to be some problem with the new image. Sometimes it appears when the article is displayed, and sometimes I see only a reference to an image. I have posted a query over at WikiMedia, and I hope to have it resolved in a day or two. Meanwhile, if you are looking for the image, please have some patience! --Aetheling 16:53, 30 September 2006 (UTC)


Addressing the original question of this section, an exponential curve does not have a constant growth rate. A constant growth rate yields a linear curve (for example, y=2x, a linear curve, has a growth rate of 2, a constant). An exponential curve has a growth rate that is, itself, an exponential curve (simplest example is y=e^x, a curve whose growth rate is equal to itself y'=e^x). For more information on this, you could visit the wikipedia page on exponential growth. I corrected the incorrect sentence.

Matt

  • You have misunderstood the meaning of the term "growth rate". When we say that a population of size X grows at a rate of 5%, for example, we mean that the growth this year will be 0.05X. If you solve the difference equation X(t+1)-X(t) = rX(t), the solution is exponential growth: X(t) = (1+r)^t X(0). I have therefore reverted your edit. —Aetheling (talk) 07:29, 12 February 2008 (UTC)

I have updated the figures for world population and world population growth rate, to reflect the latest figures and estimates from the US Bureau of the Census. I also took the opportunity to improve these charts a little. I narrowed the range of the first and converted the vertical scale from semilog, so as to bring out more detail. If you look at this chart in its highest resolution, you can see that we have been following pretty closely the UN Medium projection (though it is still way too early to make any definitive judgement on this point). For the growth rate chart I added the latest projections by the US Bureau of the Census out to 2025, in red. Cheers! —Aetheling (talk) 18:16, 19 September 2008 (UTC).


I wanted to point out that this approach to exponential growth is to limited. In the article it is suggested that you should view the population as different groups with different growth rates. You could compare a population that is decreasing with 2,5% per year with a population that consists of two groups. Lets say half of the population is a group that decreases with 10% and the other half increases with 5%. The latter would have a decrease of 2,5 percent in the first year. But this would slowly change over time. After 15 years you will see a growth of about three percent. And over time the growth of the entire population will be five percent. The group with the largest growth wins.

This is an important aspect because people will respond differently to the changes in society. There are a lot of explanations why population growth slowes when gdp rises. There will be more contraceptives and more luxury etc. However there will be a group within the population that despite all these changes still has a preference for having children. M. Meijer —Preceding unsigned comment added by Meijer1973 (talkcontribs) 20:05, 29 August 2010 (UTC)

Graph of World Population

Hmm. I just wanted to object to a few things:

  • The World Population graph is described as "clearly... close to linear". Really? To me it looks "clearly curved". (In fact, I think I see evidence of the logistic curve, but that could well be spurious.) As alluded to in the article, 50 years is an awfully short time to get a good idea of how human population levels are changing. In fact, graphing the data from 1804-1999 given in the first external link at that point in the article, would give a strong impression of exponential growth. Yes, maybe we're starting to see the beginning of the "slowing down" in growth that's predicted by the logistic model, but it's relatively early in that process, IMO, so I would be very hesitant to claim that the growth is no longer exponential — certainly not based on the data given here. (dcljr, continued below)
    • Yes, graphing the 6 points 1804-1999 does look closer to exponential (see below) - but the data prior to 1950 are extrapolations or approximations, based partly on the assumption of exponential growth prior to 1950 (and of course data after 2004 is purely extrapolated with some unstated model). Only the data highlighted in blue are based largely on actual census counts. (In any case, it looks closer still to two linear segments with an critical point near 1960). So the reason for concentrating on the last 50 years is because that is the sole period for which we have reasonably reliable data. And when you graph that real data, you get something that offers little support for the common assumption that "it's obviously exponential". Also it was not stated that it's "no longer exponential", but rather that there is no strong evidence that it ever has been. In fact it could be a very slow exponential, or maybe a very slow logistical, or perhaps linear, or quadratic - the point is we really don't know, and at any rate it certainly isn't a simple function. But at least the reason for choosing this period should be clarified. (Securiger)
      • Hmm... Part of the reason it might look closer to two linear segments is because the interpolating curve is (I assume) a cubic spline (and there's no point for it to go through between c. 1805 and 1925). Anyway, I agree with the rest of your paragraph. - dcljr 22:53, 7 Sep 2004 (UTC)
  • Note that the plot of World Population Increase suggests that the rate of increase may actually still be going up, perhaps even (approximately) linearly (you always have to expect short-term fluctuations from the overall trend), which would imply quadratic growth. (dcljr)
    • How do you figure that? Apart from two years, it has been going down every year since 1987 - which is a third of the period for which we actually have reliable data! (Overall, there has been downturn in the growth rate for 26 of the 54 years considered.) (Securiger)
  • The sentence that begins "Also the rate of increase should increase, whereas, of the increase between 1960 and today, five-sixths occurred in the early 1960s", aside from being confusing, is completely misleading, since a mere glance of the Increase graph shows something highly unusual happening in the years 1957-1962, resulting in a lcoal minimum in 1960! That dip in the graph is the only reason the statement above is true (to the extent that it is). (dcljr)
    • I'll try to rephrase the sentence you find confusing. The point is that in a positive exponential, the first difference (and second difference, and all other differences) is also a positive, upward trending exponential. Thus when you get a true exponential growth curve and plot the differences between years, that rate-of-growth curve is itself an upward curving exponential. The rate-of-growth curve for human population clearly does not look like that at all. This is seen even more so in the 2nd difference curve (below), which however I would not include on the main page because second differences are heavily affected by noise. If population was exponential, the second difference curve should also be exponential, in fact it has a lot of noise oscillating around zero but with an overall downward trend. As for the statement which you claim is "completely misleading", umm, your "objection" agrees almost exactly with the point and meaning of that sentence: if we were looking at exponential growth, most of the growth would be recent, but in fact most of the growth is due to "something highly unusual" happening back then - the big dip from '57 to '60, and also the huge surge from '60 to '63. And even if we interpolate the years '57 to '63 to remove this curious feature, 75% of the growth increase between 1950 and the peak year, 1990, occurred in the first half of that period. This is just not at all consistent with a positive exponential growth. It seems I need to make some clarifications on why this chart, and the data it represents, are wholly inconsistent with the implications of exponential growth. (Securiger)
      • Maybe I misunderstood your purpose of pointing out the circa-1960 thing. I don't know. In any case, I wouldn't read much into the data of around that time. The "hiccup" might just be "noise" or might be due to a completely administrative cause (a change, say, in how censuses were taken or recorded in one or more large countries at the time — who knows?). I think most of our "differences" can be summed up by the following statement from the article: "...short-term trends, even on the scale of decades or centuries, do not necessarily disprove the underlying mechanisms...". I've been taking a much more long-term perspective, figuring that things like the 1960-ish "hiccup" and the "decrease in the increase" since 1986 are likely short-term deviations from the overall pattern over centuries (which is essentially unknowable anyway, but at least an exponential [and logistical] model has some theoretical basis). Anyway, I think both of us can agree that in the last 50 years or so the trend has not appeared to be exponential. On a completely different note, it would be interesting to consider (not in the article itself — or even here, necessarily) what role (tele)communications and transportation plays in all of this. Might population growth be "stabilizing" (2nd derivative graph above) as a result of the increased interconnectedness of human populations? Perhaps that's the reason behind the "critical point" of around 1960? - dcljr 22:53, 7 Sep 2004 (UTC)
  • Finally, I think the correlation coefficient is a pretty useless measure of anything in this context; someone should do an appropriate statistical test on the yearly data instead (I suggest an F-test to see whether an exponential term is needed over linear [intercept and slope] terms, and possibly an approximate lack of fit test). - dcljr 08:00, 6 Aug 2004 (UTC)
    • Why do you think it is useless here? is supposed to measure the fraction of the variability in y explained by the function of x - in this case, a linear model and exponential one explain the variability about equally well. I don't understand what you mean by "F-test to see whether an exponential term is needed over linear", but an F-test finds no significant difference in the residuals from linear and exponential models. Securiger 16:58, 7 Aug 2004 (UTC)
      • Why is it useless? Because an exponential with slow growth can look linear and have a correlation close to 1! As for r², the article mentions the correlation coefficient not the coefficient of determination. Although obviously they're computationally the same in this case, the author was using it specifically to indicate linearity. In any case, even if you grant that "practically speaking" the correlation is close to 1, consider what "practice" we're putting this information to: we're using these models to predict population levels far into the future (sometimes as far into the future as we have "reliable" data in the past, in fact — see above graph) and there can be a big difference between extrapolation using a linear model and one using an exponential. (Of course. That's why we're discussing this in the first place.) Oh, and I meant an ANOVA "F-test" for testing whether a coefficient in a regression model is zero (as opposed to an "F-test" for testing the equality of two population variances). I should have been more specific. I'm not sure what "F-test" you did. - dcljr 22:53, 7 Sep 2004 (UTC)

Depletion of resources.

I think these things should be included because they strongly effect what decisions should be made regarding Malthusian theory. I find it impossible to argue with or doubt the basic theory. Almost the only requirements for its applicability are that life exists and there is no centralized control. What is in question are the time scale and the nature of the catastrophe. Both of these are strongly effected by pollution and resource depletion, especially energy and farm land. One can consider food the "fuel" of non-industrial man, so energy is the modern equivalent.

The only way I feel I am being pessimistic is that nuclear (breader fission and/or fusion) power may well be able to replace fossil fuels with acceptable pollution and hazard, but no-one is sure of that. Anyway it can't support the kind of increase in energy consumption we are seeing.

David R. Ingham

Citations Needed

There is no cite given for the following assertion:

In fact, currently, food supply per person is several times higher than when Malthus wrote his essay

Reference #10 links to the International Data Base home page, but does not contain a reference to any particular article.

Only showing to 1950 in the chart

I read what was discussed before, and I still think it is misleading to only show data from 1950-2000. Regardless of the precision of the data before 1950, the numbers can still be shown to be in the right ballpark. (One reader commented that the data before 1950 were often approxomations that, in part, assumed exponential growth - but one can not possibly assume linear growth, or there would have been no people before 1900! And the numbers for earlier dates are based on real data, not merely assumptions.)

It's obvious that the period from 1950 to 2000 looks much more linear than, say, 1750 to 2000, and gives a misleading impression. The correct answer is, as has been said, that world population appears to follow a more complex function than simple linear, exponential, or quadratic growth. So why show only the select portion that appears linear? – Quadell (talk) 13:47, 10 October 2005 (UTC)

Since there has been no discussion for 2 weeks on this, I'm going to change the article. – Quadell (talk) 15:19, 23 October 2005 (UTC)

An Inaccurate Interpretation

When you say:

"[Malthus] predicted that population growth would eventually outrun food supply,"

(this being one of many statements you've made in support of your interpretation) you seem to be claiming that Malthus was describing (and predicting) a future catastrophic global event - one that has yet to occur. That is not what he was saying, at all.

Malthus posited a doubling of world population every 25 years under ideal conditions (no shortage of food and none of the "positive" constraints of, for example, war and disease). It is wrong to assume that Malthus actually thought the world population would double every 25 years until some future event in which there would not be enough food to sustain the population. (Given his ideal conditions and a population at the close of the 18th century of 1 billion, the world population would now be in excess of 250 billion.)

What he predicted was not some apocalyptic event but ongoing catastrophes playing out simultaneously in localized areas all over the world, wherever and whenever any group of people could not sustain themselves because their population had outrun the local area's food production capacity. His intent is quite clear in his statement (when discussing the American Indian):

"Yet, [...] the effort towards population, even in this people, seems to be always greater than the means to support it." [emphasis added]

It is also implicitly clear that when Darwin found in Malthus' essay the mechanism that drives evolution - a constant competition for survival due to limited resources - he didn't think Malthus was predicting some future global catastrophe.

Malthus was addressing the idea of utopian societies gaining popularity at the time he wrote his essay. The point of his essay was to show that there could never be a population free from poverty and hunger and, therefore, the dream of a utopian society was just that - a dream. While your point that food production is now far greater than Malthus could ever imagine is true, what Malthus was saying remains valid. There are more people living in extreme poverty today than there were people (in total) at the time Malthus wrote his essay.

Paul Pomeroy 06:14, 24 December 2005 (UTC)



I was going to make those very points (see above) about the logistic curve behaviour not contradicting Malthus's ideas, i.e. that he did not predict exponential growth but rather a tendency towards it, always modified by "checks", which is precisely where the logistics curve comes from. But then, why hasn't that change yet been made?

I'd also like to draw attention to [Nassau Senior]'s work on wages, which has some of this thinking behind it. The particular point I want to bring out is his idea that machinery could theoretically compete with people for food, if only it needed fuel that drew on the same resources - which using more renewable fuels might soon cause. PML.

Population, WHEN UNCHECKED, increases in a geometrical ratio

Hi,

when discussing the correctness of the geometric growth assumption and Malthus' theory in general it's important to keep Malthus' exact words in mind: "Population, WHEN UNCHECKED, increases in a geometrical ratio". Since the late 18th century occured plenty of Malthusian' checks to the human population: wars and epidemics, unhealthy living conditions, still existing infant mortality, contraception and abortion etc.

Arguing that the Malthusian population model is void because we can't see a perfect exponential growth in the world population chart seems somewhat dubios; without considering the existence of checks (that, in Malthus' thinking, avoid, or delay, the "big catastrophe").

-- 212.144.193.196 12:01, 19 February 2006 (UTC)

user 212.144.193.196 is right on target. i wish she or he would get a name :) Anlace 21:16, 23 June 2006 (UTC)

Fertility Rate

There has been enormous decrease in female fertility worldwide and this is something that is not just specific to the west. The average worldwide fertility is now 2.59 (2.1 is the replacement rate fertility at which no population growth will occur in the long term). For instance the fertility rate in India is now 2.73. This implies that growth is not exponential since a constant fertility rate would be required for exponential growth. This is the reason for the UN estimates. A scientific approach (scientific does not mean environmentalist) implies that population growth must level off due to decreasing fertility. Therefore neo-malthusian theory makes no sense and has just been debunked. QED bitches.

the anonymous author above makes little sense. the birth rate of India for example would lead to tens of millions more people in that country in the next decades if the rate is left unchecked and death rates do not escalate severely. moreover there are many ways population growth can "level off" besides decreased fertility. thus the author above has revealed his or her inherent lack of scientific approach. Anlace 04:39, 2 July 2006 (UTC)
I'm not sure what the commenter means by 'female fertility'. There is no reason to think that women are physiologically less fertile than they used to be. The reduction in actual birth rates is due mainly to contraception, abortion, and to the increasing economic independence of women, which means they do not need to marry as soon as possible. I don't know about 'neo-Malthusian theory', but Malthus himself was aware of the primitive methods of birth control available in his day, and deplored them as immoral 'violations of the marriage bed'. His own preferred method of birth control was 'moral restraint', i.e. abstention from marriage by those who cannot afford to raise children, combined with chastity by the unmarried. Which is a bit grim, but don't forget he was a clergyman.109.158.128.2 (talk) 13:33, 20 January 2014 (UTC)

That assumes fertility does not continue to decrease and we have no reason to expect that will happen given that it has decreased from 6 to less that 3 worldwide from 1960 to 1990. You say India will continue to experience population increase. It will but at a slower rate which is completely inconsistent with Malthus. Showing an increase in population is not enough. You are required to show an exponential increase. A decrease from 6 to 3 definitely implies that growth is not exponential since exponential growth requires constant fertility.

Could we please have a moratorium on comments about Malthus by people who have never read him? Malthus never claimed that population actually increases at an exponential rate, only that it would do if there were no 'checks' on reproduction. He then devoted hundreds of pages (in the later editions of his Essay) to analyzing what those 'checks' were.109.158.128.2 (talk) 13:37, 20 January 2014 (UTC)
i think someone is missing the big picture here. have you seen the "low" projections for india and many lesser developed countries (i am not considering India lesser developed by the way). the real issue is carrying capacity. do you honestly believe there is carrying capacity for these burgeoning billions when over one billion people today do not have safe drinking water? this is not a simple matter of sharing the wealth. we are simply living on a finite planet, whose resources are stretched thinly. wake up and smell the coffee. the catatastrophe is occurring now. by the way your credibility would grow exponentially if you would create an account :) Anlace 05:15, 2 July 2006 (UTC)
Carrying capacity is a variable in the Logistic curve, it is not part of malthus' original theory afaik. Kim Bruning 09:07, 20 July 2006 (UTC)

Logistic curve and lotka-volterra

They're already mentioned, but not emphasized. Could we maybe stress that there are currently improved population models available. Both these newer models *do* actually have malthusian style exponential growth for certain parameters. They just also have different behaviour under other parameters. --Kim Bruning 09:01, 20 July 2006 (UTC)

NPOV & Factual accuracy

The section on "is the catastrophe happening?" seems to have a Non-NPOV and perhaps even some factual accuracy. I just stumbled on this article and don't know enough to necessarily correct it all myself, but tagged the section. For example, the unsourced and original opinion that the UN study is "less scientific" than contradicting studies. There are weasel words/phrases like "numerous scholars accept...", "some analysts consider...", etc. I think the section has definitely been massaged to push a subtly apocalyptic point of view.--160.39.213.64 01:54, 27 September 2006 (UTC)

I did enjoy the bit about one lone economist suggessting that global starvation might not be inevitable! Most economists (and others with a half a brain!) regard theories of Malthusian catastophes as a 19th century goof, and comprehensively disproven! Neo-Malthusianism is up there with those who believe that reading the Bible backwards reveals Satanic messages! --Nmcmurdo 19:02, 23 October 2006 (UTC)

I agree that the earlier version had some serious problems with bias. As time permits, I have been trying to improve this section with both text and figures that let readers make up their own minds based on the most impartial and accurate graphics that I can devise. — Aetheling 20:55, 24 October 2006 (UTC)

As first user states. There are lots of NPOV issues with that section. Whoever authored that section was determined to reject all notions that the Malthusian Catastrophe is shoved back/not happening at all. Then again murdo, isn't it a bit personal to talk, ad hominem, to the Neo-Malthusians? We sure could use a little tact everywhere in Wikipedia. Pasonia 03:31, 18 November 2006 (UTC)

True. The way I heard it, the world food supply is more than enough to comfortably sustain the entire population, and famine is due mostly to politics and poor distribution. Vultur 9:48 PM, 16 December 2006 (UTC)

there is no question that more sourcing is needed on this article (along with 99 percent of all wikipedia articles}. Vultur, the way you "heard it" is factually in error. the world food supply is presently being produced by unsustainable agricultural methods. in some of the biggest production areas (eg great plains of USA and north China plain) groundwater is being exhausted. there are countless other factual examples of the fact that food production is not foreseeably adequate...let alone adequate drinking water. thus i hope the zeal expressed above will translate into acquiring fact based sources. regards. Anlace 15:31, 17 December 2006 (UTC)

Malthusian catastrophe in popular culture

Maybe this article is asking for a "Malthusian catastrophe in popular culture" section, as popular on many other articles? To seed such a section, here's a piece of trivia: the Guardians of the Universe, from DC Comics, originated in a planed named Maltus, and were called Maltusians. Some of them evolved into the Guardians and left for Oa, while most stayed behind, and were later depicted as much less advanced than Earth, presumably due to Malthusian effects. It may be that the name is only a coincidence, and as such I'd rather not touch the article, but I believe it's intentional. I'm sure other people can remember lots of other pop references. LaloMartins 05:01, 12 October 2006 (UTC)

Critics of Malthusian catastrophe

Following are the sections I wrote on critics of malthusian catastrophe. However, they might first be further discussed before any display on the article page again, so I moved them here. Please state if you find them reasonable or not. Mikael Häggström 06:54, 9 June 2007 (UTC)

Economically

By the simple rule of supply and demand, an increasing population would lead to an increasing demand for food. If then the supply of food isn't increasing at the same rate, the price of food will increase. Thus, more people would find it worth to work agricultural, and if the land area of agriculture isn't enough, find alternatives for producing food. Such alternatives could be food based on algae or fungi [1] or, on the long term, purely synthetic food. On the other hand, increasing prices of food would render the consumers to find cheaper alternatives. Thus, the worst catastrophe that could happen is that all people would have to become vegetarians, instead of the wasting system of eating animals eating vegetables. Alternatively, the population would have to eat more algae or seaweed.

The problem is that you run into limits of what can physically be produced. Prolonged exponential growth would lead to absurdities like having more people than there are atoms in the universe, or a vast ball of humans expanding into space faster than the speed of light. Supply and demand isn't going to make those scenarios any less absurd. Even to get remotely close to those scenarios would require sci-fi-style technology (think Ringworld), which, while it may appear in the future, should not be taken for granted. Currently feasible things like eating seaweed would buy us a few doubling times, at best, and the population doubles every 70 years at a modest 1% growth rate.
Malthus agreed with you that agricultural output could be increased, but he didn't believe it could increase as fast as a growing population.Rsheridan6 03:25, 15 June 2007 (UTC)

Shouldn't the growing occurrence of obesity in the developing world render Malthus' theory (at least as it relates to food) void once and for all? I mean now we can manufacture junk food with ridiculously high calorie content for next to nothing. The number of obese individuals worldwide has now equalled the number of underfed. This should be mentioned somewhere http://www.fao.org/FOCUS/E/obesity/obes1.htm81.153.62.232 20:23, 10 July 2007 (UTC)

That has nothing to do with the essence of the theory. Read the paragraph above yours: where is the cheap junk food going to come from when there are 12, 24, 48, 96, or 192 billion people? The theory is based on the fundamental nature of food production and population growth, and the fact that farming productivity outstripped population growth for a century or two (really not a long time on an evolutionary or historical scale) doesn't render the theory null and void forever, any more than the fact that oil production increased for a few centuries proves that there's an infinite supply of oil in the ground. To render it void forever, you would have to either show that we can reliably have food production increases similar to the green revolution on a regular basis, or that population growth will cease forever. Rsheridan6 05:53, 11 July 2007 (UTC)

Distribution

The starvation we see on earth today isn't a result of an insufficiency of the earth to supply food, even without prospects of purely synthetic food and a shift to eating algae and fungi. Rather, it's a result of inability to transport it to all areas where it is needed. By the economic reasons above, this will continue into the future as well. Thus, there will be no deterioration of mankind due to the Malthusian catastrophe, although an unfair distribution of supply might persist.

The sections (Distribution in particular) are stating opinion as fact, and not crediting the opinion to any source. Wikipedia is a tertiary source, and must also be written from a neutral point of view. We cannot say "it's obvious that this theory is wrong because blah", we must say "John F. Doe and Dr. Foo disagree with this theory due to blah". Capi 14:55, 14 June 2007 (UTC)
Yeah, right. [1] Guess the U.N. know what they are talking about when they say that there's already enough food for 12 billion people. And the population is expected to reach a maximum of 9 billion. Actually in many parts of the world the population already stopped growing. So I don't think figuring out how to grow stuff in space is our primary problem to stop people starving and I also don't think the Malthusian catastrophe is about to happen any time soon. --Mudd1 13:44, 25 August 2007 (UTC)

Load of clap-trap

What a load of clap-trap! Even Malthus agreed that since his predicted catastrophe never happened, he was wrong. Would that his modern-day supporters were as intelligent and honest as he.

Man does not live by bread alone

In most discussions/articles RE: the sustaniability or otherwise of future (or even current) population levels there is far too much emphisis on the feasibility (or otherwise) of meeting projected demands of FOOD but what of other resources required by modern people to lead worthwhile lives like housing, clean water, clothing, energy, transport, medicine and all manner of manufactured goods. There are serious question marks over the long term availability of sufficent supplies of raw materials to meet these needs even at current population levels. And what pollution ? All other considerations being equal surely twelve billion people will produce a lot more than say two billion. 80.229.222.48 11:14, 11 August 2007 (UTC)

Population growth

http:Disablelink//www.optimumpopulation.org/ your right about this one... it is a spam one really here ... because of the donation thing pov. etc... thanks for catching that NJGW it is not a good link here at all... and I guess you agree that you probably mistakenly removed this one previously... that is excellent information M. King Hubbert on the Nature of Growth. 1974 Thanks for being alert on the other one. skip sievert (talk) 18:46, 5 September 2008 (UTC)

The Hubbert link doesn't really belong either... it doesn't mention Malthus or speak of population drops due to catastrophe. It deals with population growth. I think other editors should look very closely at that link and consider removing it. It has also been inserted into other articles recently to which it is only tangentially related. NJGW (talk) 07:33, 6 September 2008 (UTC)
Sorry I think you are wrong. It is all about exponential growth and use of resources .. and future consequences.. Why would it have to mention Malthus to be pertinent? It goes way beyond Malthus... Malthus would have swooned over Hubberts charts and graphs. Hubbert was probably was the most well known Geo-scientist produced by the U.S. -- Removing that link ... is removing very good information. Not suggested. Look at Hubberts exponential growth explanation in the article. For that reason alone it is good... also here is a sample from the paper in question:
Yet, during the last two centuries of unbroken industrial growth we have evolved what amounts to an exponential-growth culture. Our institutions, our legal system, our financial system, and our most cherished folkways and beliefs are all based upon the premise of continuing growth. Since physical and biological constraints make it impossible to continue such rates of growth indefinitely, it is inevitable that with the slowing down in the rates of physical growth cultural adjustments must be made.[2] Now that is purely Malthusian. skip sievert (talk) 15:40, 6 September 2008 (UTC)
Malthusian? Perhaps (though it's your word against Hubbert's lack of using the name Malthus for now), but how is it related to Malthusian catastrophes? Lots of folks have written works which may be traced back in some way to Malthus, but we shouldn't list every one of those papers here, or even at Malthus' article for that matter. The external links should be a stand-out resource which speaks about the topic itself, or else we'll have every single person who likes a tangentially related website wanting to link it here.
Better idea: try finding a way to use it as a ref here or at Malthus in a way which doesn't violate wp:OR. NJGW (talk) 19:18, 6 September 2008 (UTC)
E.T's are supposed to expand the information not directly in the article but pertinent.
Wikipedia does not publish original research or original thought. This includes unpublished facts, arguments, speculation, and ideas; and any unpublished analysis or synthesis of published material that serves to advance a position. This means that Wikipedia is not the place to publish your own opinions, experiences, or arguments.
How it is you interpret that file as such is not known. This is a scientist who was called before a subcommittee of the Congress to testify about energy, as it relates the environment and consequences of lack of energy in the future. Energy is what supports our system. If you loose access to it the system stops. Original research? Hubbert was called before these politicians to try and explain a very Malthusian problem... We use petrol also for making fertilizer and pesticides... That is the green revolution... or what powers it. skip sievert (talk) 20:56, 6 September 2008 (UTC)
I think you mean ELs, not ETs. In any case, you should read wp:EL, and especially the list of suggested external links and the thirteenth entry in the list of links to avoid (which reads in part "Sites that are only indirectly related to the article's subject: the link should be directly related to the subject of the article"). The article is not about Malthusian catastrophies, Malthus and catastrophies are not mentioned, and besides your interpretation we have no indication that this was essay was written to "explain a very Malthusian problem". I'm not trying to be mean, and I see why you believe what you believe (and even agree with your main points regarding Hubbert peaks and population growth), but that doesn't make it appropriate to link this essay in this and other tangentially related articles. Besides, it exists appropriately as a link in at least 6 other articles already. NJGW (talk) 21:36, 6 September 2008 (UTC)

I agree with NJGW here. The WP:OR violation he is referring to is not in the contents of the linked article itself; it's in your tacit assumption that the latter relates to the main topic of Malthusian Catastrophe. That is far from being a given. I echo his guidance in trying to place it within the body of the article. It's compliance or lack thereof will then become apparent. ~ Alcmaeonid (talk) 22:06, 6 September 2008 (UTC)

Ok... but I do not agree... peak oil is about Malthusian as it gets, in every sense. skip sievert (talk) 05:25, 7 September 2008 (UTC)
I think it's more accurate to say that some of the predictions of oil depletion resemble Malthusian catastrophes, but that's already covered here and a link to Peak oil exists in the see also section. I see no reason to violate wp:ELNO-13 in this case. NJGW (talk) 15:09, 7 September 2008 (UTC)
You have a point there. Bartlett does a good job explaining things. I am thinking now that I agree with your points in general, after looking more into the issues you discussed. skip sievert (talk) 22:33, 8 September 2008 (UTC)

Anarcho-primitivism connection?

First I just want to point out that links within the See also section shouldn't have the same level of scrutiny as those in the EL sections. That said, this connection is a bit loose... I can see how one might argue that an Anarcho-primitivist might support the return to a different lifestyle in order to avoid a Malthusian catastrophy, but couldn't the same be said for any type of primitivst? Maybe a section could be inserted in the text which discusses movements which aim to mitigate a catastrophy and primitivism could be mentioned there (but since this is essentially a population issue, a sudden drop in technology levels worldwide would create an instant and artificial--rather than organic--Malthusian catastrophy).

This seems a bit tricky, but if done correctly could improve the article. NJGW (talk) 18:11, 18 September 2008 (UTC)

It's complicated to distinguish "artificial" from "organic" social phenomenon. The connection is very clear if you consider that the "Malthusian catastrophe" is in itself part of the anarcho-primitivist theory on why civilization is unsustainable. In this sense, the anarcho-primitivists are not exactly looking to “mitigate” the problem, but to find alternatives of sustainable survival trough the inevitable collapse. Maziotis (talk) 21:05, 18 September 2008 (UTC)

Anarcho-primitivism is an anarchist critique of the origins and progress of civilization. According to anarcho-primitivism, the shift from hunter-gatherer to agricultural subsistence gave rise to social stratification, coercion, and alienation. Anarcho-primitivists advocate a return to non-"civilized" ways of life through deindustrialisation, abolition of division of labour or specialization, and abandonment of technology. There are other non-anarchist forms of primitivism, and not all primitivists point to the same phenomenon as the source of modern, civilized problems. I fail to see how this is related... much to Malthus, if at all. skip sievert (talk) 02:10, 19 September 2008 (UTC)
Maybe you should try to read more than the first paragraph of an article in wikipedia when trying to understand a subject. Maziotis (talk) 09:32, 19 September 2008 (UTC)

I believe there is not exactly a Marx in anarcho-primitivism like there is one in marxism. There is this general assumption that civilization is a two second disease in our biological history. Other than that, there is a space for different interpretations to what the unsustainability of civilization means. I never meant to argue that the Malthusian theory is a corner stone in anarcho-primitivist theory. Simply, if I understood it well, this theory is an explanation on how agriculture is unsustainable for human beings in the long run. This in turn is central to a political philosophy called anarcho-primitivism. There is where I see a clear connection. Maziotis (talk) 11:52, 19 September 2008 (UTC)

Yeah probably that is the angle that would have to be tried to get at... if a link were to be made. As NJGW said Maybe a section could be inserted in the text which discusses movements which aim to mitigate a catastrophy and primitivism could be mentioned there (but since this is essentially a population issue, a sudden drop in technology levels worldwide would create an instant and artificial--rather than organic--Malthusian catastrophy).... Another section might list a bunch of alternative concepts... but still Anarcho-primitivism being in my opinion... a kind of political social movement... that is possibly a couple of steps from even mainstream hetorodox thinking, although I am familiar with Tainter and his ideas, and also some of the other well known advocates of this movement. skip sievert (talk) 14:25, 19 September 2008 (UTC)

does not belong in lede

"An August 2007 science review in The New York Times raised the claim that the Industrial Revolution had enabled the modern world to break out of the Malthusian Trap,[1] " ... uh... the idea the that the Industrial Revolution enabled the modern world to break out of the Malthusian Trap goes back to ... well, shortly after Malthus. Certainly it was widely accepted among economists by the early 20th century. And that's way, way, way before 2007. This is so outdated (2007 vs. 1900) and trite ("raised the claim" to characterize a widely held view completely supported by empirical evidence) that it just does not belong in the article, and definitely not in the lede.radek (talk) 22:23, 1 August 2009 (UTC)



I am curious if Malthusian theory can be applied to other areas of growth. For example, educational institutions continually birthing graduates in relation to the number of jobs available. In trying to ease the problem, different organizations or government entities are wanting to create new jobs. This is not stated as reality but to only an example. Beetlebailey75 (talk) 09:01, 3 April 2010 (UTC)beetlebailey75

This sentence is questionable

"In some cases, population growth occurs due to increasing life expectancies, even though fertility rates are below replacement."

Does not seem to make mathematical sense. The mechanism where increasing life expectancies creates population growth works in the way that: greater life expectancies cause increasing fertility rates, which causes population growth. Increasing life expectancies cannot create population growth without increasing fertility rates about replacement first. Think about the arithmetic of it:

If you have an initial number, say, 0, and can (only) add or subtract as many 1s from it anytime, you need to add more times than you subtract to get a greater number. I'm no mathematician, by the way, so I don't know if this is always true, but I'm pretty true it applies here. Anyways, if "fertility rates are below replacement," as in the sentence in question, it corresponds to subtracting more times than adding, if the resulting number corresponds to the population, but since you need to add more times than you subtract to get a greater number, the population could only decrease. If the population could only decrease, it wouldn't make sense how "population growth occurs". If no one objects, I'll remove this statement at February. 173.180.202.22 (talk) 06:36, 2 January 2012 (UTC)

And also, the example where there's "1.3 children/woman" doesn't seem to be a replacement rate because the children's parents don't necessarily have to be replaced. 173.180.202.22 (talk) 07:10, 2 January 2012 (UTC)

Rename

Wouldn't it be better to have this article, with a slight rewrite and shift of focus, under Malthusian theory (currently a redirect here) rather than "catastrophe"? The way the idea works is that there are demographic checks on income per capita but a "catastrophe" in the sense of something sudden and very bad is not necessarily a consequence of the model.VolunteerMarek 08:13, 4 July 2012 (UTC)

  1. www.ias.ac.in/resonance/May2004/pdf/May2004p33-40.pdf