How to perform clustering of two different sets of entities?

Question

I need to perform clustering of two different entities. Lets say we have transmitters and users. The relation between a transmitters and user is defined by a weight, for example, the weight between transmitter $t$ and user $u$ is denoted as $w_{t,u}, t=1,2,\cdots, T, u=1,2,\cdots, U$.

1. Maximum cluster size (in terms of number of transmitters). There is no such constraint on the user number in a cluster.
2. Clusters are mutually exclusive. one user or transmitter can belong to only one clusters.
3. All the transmitters in a cluster serve only their own users.
4. The user must belong to a cluster that has the transmitter providing the highest weight for the given user.

The clustering objective is the maximise the signal quality of all the users. The signal quality for user $u$, $q_u$ is defines as

$q_u=\frac{\text{Sum of weights for all the transmitters in user cluster}}{\text{Sum of weights for all the transmitters not in user cluster}}$

Therefore, the objective is $\max \sum_{u=1}^Uq_u$

I am looking for optimal as well as some goo heuristic approach.

Note: We do not have access to coordinates of the users, however have access to the coordinates of the transmitters. As mentioned, the weights are also known.

Answer 1

This can be formulated as a MIP model using a gaggle of binary variables. First, we introduce some parameters. $\tau(u)$ is the index of the transmitter with highest weight for user $u$. I will charitably assume this is unambiguous (no ties for closest transmitter). $\overline{Q}_u$ is an upper bound on the possible values of $q_u$ for user $u$. $C$ is the maximum number of transmitters in any cluster and $L$ is an upper bound on the number of clusters.

Let $x_{t,t'}\in \lbrace 0,1 \rbrace$ be 1 if transmitters $t$ and $t'$ are in the same cluster, 0 if not, for $t\neq t'$. $x_{t,t}$ will be 1 if transmitter $t$ "anchors" a cluster and 0 if not. A cluster has exactly one anchor.

Let $y_{t,u}\in\lbrace 0,1 \rbrace$ be 1 if user $u$ is in a cluster with transmitter $t$ and 0 if not.

Here come the constraints. First, we require that the $x$ variables be symmetric (if $t$ is in the same cluster as $t'$, then $t'$ is in the same cluster as $t$):$$x_{t,t'}=x_{t',t}\quad\forall t\neq t'.$$

We also need to enforce transitivity. If $t$ and $t'$ are in the same cluster, and $t$ and $t''$ are in the same cluster, then $t$ and $t''$ are in the same cluster. So we add the following constraints. $$x_{t,t''} \ge x_{t,t'} + x_{t',t''} - 1\quad \forall t,t',t'' \ni t\neq t' \,\&\, t' \neq t'' \,\&\, t \neq t''.$$

We must force every transmitter to belong to a cluster with an anchor, which requires additional variables $v_{t,t'}\in [0,1]$ where $t\neq t'$. The additional constraints are $$v_{t,t'} \le x_{t,t'} \quad \forall t\neq t'$$ $$v_{t,t'} \le x_{t',t'} \quad \forall t\neq t'$$ and $$x_{t,t} + \sum_{t' \neq t} v_{t,t'} = 1.$$ So if $t$ is an anchor ($x_{t,t}=1$), $v_{t,t'}=0$ for all $t' \neq t$; but if $t$ is not an anchor ($x_{t,t}=0$), then $v_{t,t'} =1$ for exactly one $t'\neq t$, and that transmitter $t'$ must be an anchor ($x_{t',t'} = 1$).

We can limit the number of clusters by limiting the number of anchors: $$\sum_t x_{t,t} \le L.$$ (Change that to an equation if you need exactly $L$ clusters.)

The following constraint enforces cluster capacity limits: $$\sum_{t'=1}^T x_{t,t'} - x_{t,t} \le C - 1\quad \forall t.$$This says that the number of transmitters other than $t$ in the same cluster with $t$ is at most $C-1$.

To avoid having multiple anchors in a single cluster, we enforce the following:$$x_{t,t} + x_{t',t'} + x_{t,t'}\le 2 \quad\forall t < t'.$$

Next, we enforce the requirement that each user belong to the cluster containing the best transmitter:$$y_{\tau(u),u} = 1 \quad\forall u.$$To determine what other transmitters serve $u$, we add the following:$$y_{t,u} = x_{\tau(u),t}\quad\forall u,\forall t\neq \tau(u).$$

The objective remains to maximize $\sum_u q_u$. To linearize $q_u$, we introduce variables $z_{t,u}\in [0, \overline{Q}_u]$ for all transmitters $t$ and users $u$, along with the following constraints:$$z_{t,u} \le \overline{Q}_u y_{t,u} \quad\forall t,u$$$$z_{t,u} \le q_u + \overline{Q}_u(1-y_{t,u})\quad \forall t,u$$and$$z_{t,u}\ge q_u - \overline{Q}_u(1-y_{t,u})\quad \forall t,u.$$ The net effect of these is that$$ z_{t,u}=\begin{cases} q_{u} & y_{t,u}=1\\ 0 & y_{t,u}=0 \end{cases}.$$ Finally, we linearize the definition of $q_u$ via the constraints $$\sum_t w_{t,u} (q_u - z_{t,u})=\sum_t w_{t,u}y_{t,u}\quad\forall u,$$which is the result of multiplying both sides of the definition of $q_u$ by the denominator and then simplifying.

Addendum: There's a bit of inherent (undesired) symmetry in the model. If you take any solution and change the "anchor" transmitter in a cluster to a different member of the same cluster, you get the same results but the solver sees it as a different solution. To avoid that, the following optional constraints can be added:$$x_{t',t'} \le 1 - x_{t,t'} \quad \forall t < t'.$$This forces the lowest index transmitter in each cluster to be the anchor. Whether these speed up the solver or not is an empirical question.

Addendum2: Details of both this and an alternate (and apparently less efficient) MIP model, along with construction and improvement heuristics that seem to work really well, are given in a blog post. The blog post also contains a link to my Java code.

Answer 2

In preliminary tests, a greedy heuristic seems to do rather well for the problem.

The greedy heuristic I tried starts out with each transmitter being a cluster of size 1, and then loops indefinitely. In each pass through the loop, all pairs of clusters are considered for merging. Any merger that would result in a cluster that exceeds the cluster size limit is discarded. The surviving candidate mergers (those meeting the size limit) are evaluated for how they would change the objective value, and the best possible merger is retained. If the best merger results in a net gain, it is implemented and the loop repeats. If the best merger results in a net loss but the current number of clusters exceeds the limit on cluster count, it is implemented anyway (and the loop repeats). You exit the loop when either (a) you are within the limit on number of clusters and there are no beneficial mergers or (b) you have too many clusters but there are no legal mergers (in which case the heuristic has failed to find a feasible solution).