# Heuristics, methods to speed up searches over subsets of big set (combinatorially NP hard probably)

I have a reasonable-sized set of size N (say 10 000 objects) in which I am searching for groups of compatible elements. Meaning that I have a function y = f(x_1, x_2, x_3, ..., x_n) returning bool 0/1 answer whether n elements are compatible. We are interested in executing this search on each subset smaller than 8 elements of N. Which is obviously either NP hard or close to this. Even for pairwise search for n elements set we have n^2 pairs to explore, which is somehow doable yet still grows quite fast for big sets. Yet then it goes nasty when we are looking for triples (identifying 3-element cliques) and quadriple or greater magnitudes.

Would you suggest any machine learning approach to help with this task? Maybe at efficiently sampling the search-space and identifying which subsets to search on, maybe fast heauristic evaluations of the function to direct the searches.

• I don't think any ML can help without additional simplifications and/or data-specific relations. For example, can we assume that there is some binary relation between pairs of elements which are compatible, and that this relation is transitive? That would at least allow you to make the process incremental. Also an important question is whether it's a requirement to find all such compatible groups: if yes that would require an exhaustive search anyway (assuming there are no additional constraints that can be used). – Erwan Jul 29 at 13:56
• thanks, well I manage to train the classifier to quite well identify on the generic attributes of elements to see if they are compatible, it allowed to reduce the search by order of magnitude, but still requires to search all pairs. If I want to go through all the triples.... well that is something we not want. – Intelligent-Infrastructure Jul 29 at 14:02
• I can only give you vague ideas: one would be to see if it's possible to apply clustering on the elements in order to reduce the number of candidate sets. Another idea would be genetic algorithms, but I think that would make sense only if the goal is to find some compatible groups, not all of them. – Erwan Jul 29 at 14:23