4 ms·
85,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.
by excalibur 9y ago
85,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.