Which machine learning models are rational to use on NP-hard and NP-complete "theoretical" problems?

Question

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?

Answer 1

Is there any point in using machine learning algorithms on these "well-defined" NP-hard problems (instead of using dynamical programming)?

In short, yes. Consider that for whatever problem you can generate data (in this context, instances of the problem), and that the "classical" algorithms (**) that solve them have hand-made heuristics you can likely employ ML to lean from data either an improved heuristic or the whole algorithm. (**I refer to classical as non-ML algos.) To understand more, I suggest this survey.

ML allows to map a given state (or partial solution) of the problem to a certain quantity that can be a number or an improved solution. A popular way to solve NP problems using ML is to leverage Reinforcement learning (read this) which, ideally, can find an approximated solution that is very close to the optimal by being guided by a reward that is a way to evaluate the goodness or badness of the current solution.

I also found some more works on graphs (here and here). Anyway, I'm not super expert on this particular sub-field so I'm not completely sure if with ML/RL you can at all find the optimum for a NP-hard or NP-complete problem, in reasonable time (although with a long training), but for sure you can devise a relaxation of the problem and then use ML to solve it without designing a specific algorithm by hand.

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?

I think that with ML, you don't need to distinguish between NP-hard and NP-complete nor you devise the algo since it's learned from data.