4 ms·
> The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible. I think this statement is not true. TSP
by nagVenkat 9y ago
> The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible.
I think this statement is not true. TSP can be solved to optimality when the number of cities is small^. GuRoBi and CPLEX's mixed integer solvers can solve TSPs when the number of cities is small. In fact [1] gives the largest TSPs solved. Now solving them fast is a totally different question and I feel like this distinction needs to be made
^ in a reasonable amount of time.
[1] http://www.math.uwaterloo.ca/tsp/pla85900/index.html http://www.math.uwaterloo.ca/tsp/pla85900/index.html
- deleted 9y ago[deleted]
- excalibur 9y ago85,900 is a small number of cities? The US has 19,354 "incorporated places", which balloons to around 35,000 if you include unincorporated towns.
- nagVenkat 9y agoI am sorry. By small I meant more like 20 cities. You can formulate a simple optimization problem and solve it with lot of commercially available solvers if you have few cities. The point i was trying to make is that TSPs are not infeasible. They can be solved to optimality given enough time. If I am not wrong, Concorde TSP solver which is a specialized solver, solves TSPs which have large number of cities.
- Retra 9y agoAn efficient solution to TSP would require an efficient solution to all instances of the problem, not an efficient solution for some instances. Most problems are easy in the small cases. And if you are solving special cases, you are solving a decidedly different problem. >They can be solved to optimality given enough time. I'm not sure what you mean by this. TSP is infeasible in the sense that it cannot be solved in an efficient amount of time. Naturally, it is solvable if you're given "enough time". It's not an impossible problem.
- nagVenkat 9y agoI should have worded my response better. What I meant was TSPs are intractable. But the author used the word infeasible. In optimization, infeasible and intractable convey different meanings.
- grogenaut 9y agoYou know tsp doesn't just mean cities or actual sales people right? It can apply to lots of things like 3d printer head or other toolpath optimization and hundreds of other problems maybe millions
- bowmessage 9y agoObviously -- but that's not what the article is arguing is impossible.
- freyir 9y agoInfeasible, not impossible.
- SomeStupidPoint 9y agoAlso, there are lots of specific configurations of cities for which an optimial solution can be found in a tractable amount of time -- it's only the general case that is the problem, and there's some debate about how "degenerate" real world examples are. In "well-behaved" cases, a good approximate answer will be the answer; in almost all cases, the differences between a good estmate and the correct solution is small relative to the total path (and so the difference is of limited importance). I often find that optimization problems suffer from trying to optimize the general problem rather than using the constraints present in the real world. TSP is similar to Turing machines and the halting problem -- in practice, it really doesn't matter.