Algorithm for best subset of items

Question

I have a matrix M with size NxN where each position M(i,j) is an integer representing the relationship between item i and j. If i and j are the same item then the positions M(i,j) and M(j,i) are 0.

What I'd need is to regroup these N items in subgroups of 5 elements each one. The value of each group would be Σ(M(i,j) for each i, j in the group).
And I would need to maximize the total value of all groups.

I studied lots of algorithms more than 15 years ago and I forgot the most of them, and nowadays are lots of new algorithms, so I'm a bit lost trying to find the best one for these case.

A friend told me to investigate Clustering algorithms but they have lots of different versions and specializations, so I don't know which one to look at first.

And just one more thing, besides this algorithm to maximize each group, would I need an algorithm to maximize the total value of all groups, discarding the non optimal selections? I remember algorithms that made this but I don't even remember their name.

Answer 1

The amount of possible combinations grows very large, even with relatively small values of N, so one thing you could consider is some variant of the local search if that's acceptable. Such algorithms are not guranteed to find the global optima though.

You need two things for this: a cost function and a neighborhood relation. The cost function you already gave and the neighborhood relation can be something as simple as swapping two elements between groups.