How to solve this clustering problem with heuristic or meta-heuristic approach?

Question

I have clustering problem with servers and users. This is different to the one posted in https://math.stackexchange.com/questions/4088441/what-will-be-an-efficient-joint-clustering-solution-to-this-problem/4090360?noredirect=1#comment8537059_4090360.

There is a link gain between a server and a user. The farther away the user is, the lower the gain. Sometimes, there is zero gain is the distance between a user and server is too high. We do not want to put one user in a cluster where the user has zero gain for one of the servers belonging to user cluster.

I want to form the cluster such that the users have better overall gain. Also, we prefer that the servers are closer to each other to reduce the overall communication delay as the servers may need to communicate to each other.

The clustering constraints I have are as follows:

1. There is a maximum cluster size limit.
2. Minimum cluster size is one.
3. The number of clusters is variable.
4. Since there is individual cluster size limit, there exists a number that dictates the minimum number of clusters the system can have, which is number of servers/maximum cluster size.

The objective is to maximum the overall gain of the whole system, which is the sum of individual user gains.

User gain is decided by sum-gain from its own cluster servers divided by sum of the gains from the remaining servers in the system.

Answer 1

[I'm leaving out constraint 0]

I see two levels of decisions in your problem:

1. Group servers into clusters
2. Assign each user to one of these clusters

(BTW, this way of seeing the problem is heavily inspired by Facility location problems).

The second step is actually the easiest: once the clusters are known, you can just compute each user's gain w.r.t to each cluster, and assign it to the best cluster. Note that if you introduce some capacity constraints, e.g., server $k$ can serve at most $N_{k}$ users, then you complicate the user $\rightarrow$ server assignment, but it's still very tractable.

So the "hard" part is how to cluster the servers together. There are many approaches for doing so, such as greedy heuristics, K-means variants, etc... For instance, you could generate $1{,}000$ different clusterings of the servers, then compute an optimal assignment of the users for each, and pick the best solution.

You could also plug this into an exploration mechanism, where you perturb the clusters (e.g. move one server from a cluster to another).

All these methods are purely heuristic, are relatively easy to implement and should scale quite well.