11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – prubin Jan 11 at 19:33
  • $\begingroup$ 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. $\endgroup$ – prubin Jan 11 at 19:37
  • $\begingroup$ 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. $\endgroup$ – dhasson Jan 12 at 16:58
  • $\begingroup$ @prubin: 1) the slash means such as and not divide. 2) I will have a proper look, thanks, any suggestion is very welcome. $\endgroup$ – Betty Jan 13 at 10:05
  • $\begingroup$ @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. $\endgroup$ – Betty Jan 13 at 10:09
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the global approach of solving the problem, I was thinking about a similar approch. However, my question is how to implement the left-hand of my constraint, either as part of constraint or as an objective function expression. I am wondering if there are any simplification techniques or algorithms to code this expression in Java and calling CPLEX. $\endgroup$ – Betty Jan 13 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.