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

Question

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: 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.

Answer 1

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group).

Standard MILP models don't scale well and I would formulate this as a set covering model, one variable for each (!) potential cluster, and solve that one by branch-and-price. I would use the left hand side of the non-linear constraint as objective function in the pricing problem and use some tailored algorithm to find the minimum reduced cost clusters. In the master problem I would minimize the maximum of the selected clusters' costs.

Solving the master problem (a linear program) can be done in CPLEX, also the tailored pricing problem can be done in your Java code, however you would not be able to have a tailored branching which you might need to solve the model to integer optimality.