The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.
Comments
I agree with grandparent that non-optimal solutions are often enough.
But just to be complete, since TSP was mentioned here:
We could solve TSP instances with >80k cities to optimality back in 2006:
https://www.math.uwaterloo.ca/tsp/
The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.