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{equation} \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} \end{equation}

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:

\begin{equation} \forall k \in \lbrace 1, m \rbrace , \forall i\in \left\{2, N\right\}: D_k \leq D^* \end{equation}

• Max distance to the leader:

\begin{equation} \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^{**} \end{equation}

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.