I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as shown in the figure. I haven’t drawn all the edges so as not to make the figure messy. Generally, the edge between the nodes that are far away from each other has low weight.
I need to perform clustering of these nodes. Lets say we want to put the nodes in 7-8 clusters/groups.
The objective is that the sum-weight in each cluster should be maximized. This may also generate clusters where the number of edges connecting two clusters is low.
Problem Statement:
Let $N=500$, $G=8$ and maximum cluster/group size is 70.
Let
binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,G\}$,
binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$.
We want to maximize $$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}$$ subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \tag1 \\ \sum_i x_{i,g} &\le 70 &&\text{for all $g$} \\ y_{i,j,g} &\le x_{i,g} &&\text{for all $i<j$ and all $g$} \\ y_{i,j,g} &\le x_{j,g} &&\text{for all $i<j$ and all $g$} \\ \end{align}
As we can see this a binary integer programming problem and has large number of optimization variable. Difficult to solve. Also I cannot afford a solver.
I prefer a less-complex solution.