# k-means/k-medoids Clustering Implementation in CPLEX Java

I am trying to model a grouping algorithm as k-means clustering problem, by referring to the general definition as mentioned in Wikipedia.

In my system, I have $$N$$ nodes that I want to group in $$m$$ groups, based on the peer-to-peer distance $$D_{i,j}$$. $$D_{i,j}$$ are known (i.e. inputs) for the optimization problem. For this purpose, I define these decision variables:

$$L_i^k$$ : Boolean variable equal to $$1$$ if node $$i$$ is the leader of group $$k$$; $$0$$ otherwise.

$$X_{i,j}^k$$ : Boolean variable equal to $$1$$ if node $$i$$ is the leader of node $$j$$ in group $$k$$; $$0$$ otherwise.

$$D_k$$: Average distance of group $$k$$: $$D_k = \mathop{{}\mathbb{E}} [ L_i^k D_{i,j} \quad / i = L \cap G_k, \ j \in G_k, j \neq i ]$$.

such as $$i,j \in \lbrace 1, N \rbrace$$, $$k \in \lbrace 1,m \rbrace$$ and $$G_k$$ is the set of elements in group $$k$$.

The following constraint aims at selecting the members of the same group such as the distance variance does not exceed $$\sigma_D$$ (known):

$$$$\begin{split} &\forall k \in \lbrace 1, m \rbrace , \forall i\in \left\{2, N\right\}: \\ &\sum_{j=1, j \neq i}^{N} L_i^k \times {\left\Vert X_{i,j}^k \times D_{i,j} - D_k\right\Vert}^2\leq \sigma_D \end{split}$$$$

My question is how to solve the optimization problem using a solver? Namely, I have implemented my optimization problem using CPLEX Java API, but I am a little stuck in this constraint. I am thinking of linearizing it but I can't figure out yet if it is a good option since I have already linearized some constraints (by introducing a new decision variable $$Z_{i,j}^k = L_i^k \times X_{i,j}^k$$ and adding equivalent linearization constraints.

Any guidance to build an efficient implementation is very welcome!

UPDATE:

The updated formulation of the k-medoids constraints, expressed as:

• Average distance to the leader:

$$$$\forall k \in \lbrace 1, m \rbrace: D_k \leq D^*$$$$

• Max distance to the leader:

$$$$\forall k \in \lbrace 1, m \rbrace, \forall i\in \left\{2, N\right\}: \max_{j=1, j \neq i} ( L_i^k \times X_{i,j}^k \times D_{i,j} ) \leq D^{**}$$$$

such as $$D^{*}$$ and $$D^{**}$$ are thrshold distances on average and max distances to the leader, respectivly. In this case, it is straithforward tomiplement it in CPLEX using java.

• I'm having trouble understanding your formula for $D_k$, in particular the reason that you divide by $i$, the index of the leader in the cluster. – prubin Jan 11 '20 at 19:33
• Also, I think your variance bound is expressed incorrectly. If $X^k_{i,j} = 0$, you end up squaring $\|-D_k\|$ when the variance contribution of that term should be 0. – prubin Jan 11 '20 at 19:37
• I don't understand how this relates to the k-means clustering, as in that case the cluster centers can be any point (not limited to the members of the dataset). Are you sure you don't mean to use another kind of algorithm, like the k-medoids algorithm? I'm not sure the current approach would be an implementation for the k-means algorithm (as the title of the question suggests), the first step would be to create variables associated to the cluster centroids. AFAIK, there's no concept of group leader for K-means. – dhasson Jan 12 '20 at 16:58
• @prubin: 1) the slash means such as and not divide. 2) I will have a proper look, thanks, any suggestion is very welcome. – Betty Jan 13 '20 at 10:05
• @dhasson: thank you for your feedback. Actually in my problem, the centroids are members of the node set so we may call it k-medoids problem; but still there is a big similarity between the two problems, I beleive my question is within the common part of the two. PS: I will update the title accordingly. – Betty Jan 13 '20 at 10:09