[stncls]

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.