I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.
I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.
I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing... My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus. My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.