[baq]

The true benefit of being able to tell NP-complete/NP-hard from the garden variety bucket-o-bytes moving is not in giving up when you encounter them, as you correctly identified, but in knowing that even attempting an optimal solution is futile and proceeding to looking for approximate solutions to the business problem more or less instantly.

People unfamiliar with the matter may attempt to solve the problem, might even get rewarded for effort and hard work if management is also unfamiliar with the matter. Maybe it's fine though...?

[travisjungroth]

Optimal is overblown for business problems in general. Knowing there’s a mathematically optimal solution, people want it. Even if it’s practically impossible to get. It feels like if you have the optimal, you don’t have to consider trade offs (not usually true).

Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable.

Anyone ever notice how these CS problems are rarely famous business problems? It’s because the pure problems don’t usually matter and the approximate versions are usually quite easy. You almost never need the shortest route for a salesman, or need to pick a secretary with no chance of going back.

[baq]

I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)

[theamk]

I would not be so sure.

What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute.

So something like a better way to arrange packages in truck, or better traffic preidiction model, would be much more useful than any TSP improvements.

[0] https://www.reddit.com/r/UPS/comments/89zw0h/how_long_does_o...

[ilyagr]

No individual truck would notice the difference. But averaged over many trucks and many days, it should result in a measurable change in gas spending.

[adwn]

The problem is that in practice, you don't have complete information, and the information you have is slightly incorrect. You also don't have a complete model, and the model you have is slightly incorrect.

[travisjungroth]

Throw on a few more decimal places if you like. The point is that in the physical world, “best” isn’t usually categorically different from “extremely close to best with high probability”.

[jacquesm]

Yes, exactly this. You don't need the optimal solution in most cases, you just need a solution, and if it is 9x% there then the optimum solution can be approximated by burning more cycles but from an economics perspective you may well already have a viable solution in hand.