Comment by arnsholt
You can encode travelling salesman as an ILP problem, so it’s a pretty tricky problem.
You can encode travelling salesman as an ILP problem, so it’s a pretty tricky problem.
The np-completeness of it is often not very relevant for practical concerns, as the parent post was mentioning.
There are many applications with an underlying technically np-complete problem for which optimal solutions are easily found for almost all instances you will encounter. Because they are np-complete it's possible to construct instances which aren't efficiently solvable, but that doesn't mean you'll ever even encounter one in practice.
Then even beyond that there are plenty of cases where an efficient approximation with bounded error exists, and that bounded error might be arbitrarily small.
To give an easily understood example, consider a knapsack problem where the items are never larger than 1% of the knapsack size.
There exists a trivial O(N log N) approximation algorithm: sort by value per size, include in that order until no more fit. This yields an optimal solution when the last selected item exactly fills the sack, and otherwise it yields an approximate solution which is suboptimal by no more than the unfilled space, which is no more than 1% due to the size constraint. And 1% is the worse case approximation error, normally less space will be unused and the lowest value per space will be a fraction of the highest value per space, so the actual average approximation error in a real application may be, say, 0.01%. If some other application constraint meant the item sizes would always add up to the sack size then the simple algorithm always gives an optimal solution.
Of course, you can do better than the simple algorithm with some search but even the dumbest algorithm gives very good approximations and is sometimes optimal... and yet the general knapsack (even just the decision form) is a problem which is np-complete. This insight can be quite surprising to anyone who assumes np-complete == unsolvable.
Complexity theory is awesome but it can also lead us astray.
This is actually a pretty poor example because we can solve huge TSP instances to optimality in practice (see the concorde solver). There exist many more tricky Combinatorial problems such as packing or covering problems that are typically much harder to solve to optimality.