Time and time again I run into "surprising" NP-hard problems that seem naturally simpler than they are. I recently worked on a weighted graph theoretical problem where the point is to maximalize a function by "selecting" edges in a proper way, which turned out to be an extension of the Subset sum problem (the basic idea is that in both problems, you can select values from a set and check if their sum can equal a specific number). Both of these problems seem mesmerizing to me, that they are so simple with barely any input, and yet NP-hard. In the title I use the word "theoretical" on these "closed set of possibilities" problems to partition them from "industrial", computationally challenging problems (like optimizing some economic target, where it's not even clear what input the target depends on). I was always interested in how these problems can be tackled efficiently (in the case of evaluating the correct answer and approximations).
Common approaches I believe include convex optimization with methods like the ellipsoid or simplex method (correct me on these), not sure about non-convex optimization, I assume it is not very popular. I've seen that the SSP can be solved pseudo-polynomial time with dynamical programming. Then there is the TSP, also NP-hard but some popular versions are only NP-complete, wondering how those set of problems are dealt with commonly.
My set of questions are:
Is there any point in using machine learning algorithms on these "well-defined" NP-hard problems (instead of using dynamical programming)? If yes, which models are recommended (like gradient descent, or neural networks exclusively)? The same as 1), but on NP-complete problems. If I randomly run into an NP-hard or NP-complete problem for which I have to design an efficient, but accurate algorithm, usually which method is most advised for tackling the problem?