How to partition a graph with optimal number of groups?

Question

I have a graph with $N=12$ nodes. Some nodes may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is maximised.

Let the weight matrix is given by $W$ of size $N\times N$. The diagonal elements of $W$ are ones, therefore, if there is no edge between two nodes, the corresponding element in $W$ is 1.

Each part can have maximum 3 nodes and minimum 1 node. I want to find the optimal number of parts, and the nodes belonging to each part.

I want to find the partition that gives the maximum total weight sum.

• If there is only one node in a part, its weight sum is one.
• If there are two nodes in a part, then the weight sum is 1+1+weight between the nodes.
• If there are three nodes in a part, then the weight sum is 1+1+1+weights among the nodes.

EDIT: Data Sample

$N=15$

w={{0   0.0246848918296812  0.0222939272001262  0   0   0   0   0   0   0   0   0   0   0.0222250595626355  0},
{0  0   0.0223369829389658  0   0   0   0   0.0222127811912141  0.0222755933905518  0   0   0   0.0221795079043392  0.0223864339914097  0},
{0  0   0   0   0   0   0   0   0   0   0   0   0   0.0224654059932641  0},
{0  0   0   0   0.0228810151692974  0.0263781458115140  0   0   0   0   0   0.0225237815238005  0.0222085450604959  0.0224040301919779  0.0221851115072885},
{0  0   0   0   0   0.0221812062988533  0   0   0   0   0   0   0   0   0.0221772974146853},
{0  0   0   0   0   0   0   0   0   0   0   0.0221782447553519  0.0221942685958015  0   0.0221829507373709},
{0  0   0   0   0   0   0   0.0225053331512079  0.0239075792682171  0   0   0   0   0.0222343245946427  0},
{0  0   0   0   0   0   0   0   0.0224947575431974  0.0259331832060178  0   0.0227525834204816  0.0223768752560173  0.0223839654721248  0},
{0  0   0   0   0   0   0   0   0   0   0   0   0.0223333187890952  0.0233707396802904  0},
{0  0   0   0   0   0   0   0   0   0   0.0247836632820100  0.0231195566008868  0.0237113172691831  0.0224461979778054  0.0222144718706271},
{0  0   0   0   0   0   0   0   0   0   0   0.0359523557525197  0.0232883288308498  0   0.0285710707914430},
{0  0   0   0   0   0   0   0   0   0   0   0   0.0221951174734581  0.0223024273663844  0.0225769922365633},
{0  0   0   0   0   0   0   0   0   0   0   0   0   0.0237292800085860  0.0222613790897664},
{0  0   0   0   0   0   0   0   0   0   0   0   0   0   0},
{0  0   0   0   0   0   0   0   0   0   0   0   0   0   0}}

Answer 1

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$. You 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 3 &&\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}

This formulation assumes the edge weights are nonnegative. In that case, you can optionally relax the equality constraint $(1)$ to $\le 1$. If instead the edge weights might be negative, you also need to impose $$y_{i,j,g} \ge x_{i,g} + x_{j,g} - 1 \quad \text{for all $i<j$ and all $g$}$$

For solvers that don't exploit symmetry with respect to $g$, you might want to add symmetry-breaking constraints. For example, you can impose descending order of group weight as follows: \begin{align} z_g &= \sum_{i,j} w_{i,j} y_{i,j,g} &&\text{for all $g$} \\ z_g &\ge z_{g+1} &&\text{for $g<N$} \end{align}

---

Applying Dantzig-Wolfe decomposition with one block per group yields identical blocks and a set partitioning formulation that you can solve via dynamic column generation (specifically, branch-and-price with Ryan-Foster branching). By the way, the SAS decomposition algorithm does this for you automatically. An alternative approach is to use static column generation, as follows. Let $G$ be the set of all potential groups (node subsets of sizes $1$, $2$, or $3$). For $g\in G$, let $N_g$ be the nodes in group $g$, let $E_g$ be the edges in group $g$, and let binary variable $u_g$ indicate whether group $g$ is used. The problem is to maximize $$\sum_{g\in G} \left(\sum_{(i,j)\in E_g} w_{i,j}\right) u_g$$ subject to \begin{align} \sum_{g\in G:\ i\in N_g} u_g &= 1 &&\text{for all $i$} \tag2 \end{align} For $N=15$, this set partitioning formulation has $|G|=N+\binom{N}{2}+\binom{N}{3}=575$ variables and $15$ constraints, and the symmetry with respect to group is avoided. If the weights $w_{i,j}$ are nonnegative, you can omit the $N$ groups of size $1$ and relax the set partitioning constraint $(2)$ to a set packing constraint (replacing $=1$ with $\le 1$).

By request, here is the SAS code for the static column generation formulation:

data indata;
   input i j w;
   datalines;
 1  2 0.0246848918296812
 1  3 0.0222939272001262
 1 14 0.0222250595626355
 2  3 0.0223369829389658
 2  8 0.0222127811912141
 2  9 0.0222755933905518
 2 13 0.0221795079043392
 2 14 0.0223864339914097
 3 14 0.0224654059932641
 4  5 0.0228810151692974
 4  6 0.0263781458115140
 4 12 0.0225237815238005
 4 13 0.0222085450604959
 4 14 0.0224040301919779
 4 15 0.0221851115072885
 5  6 0.0221812062988533
 5 15 0.0221772974146853
 6 12 0.0221782447553519
 6 13 0.0221942685958015
 6 15 0.0221829507373709
 7  8 0.0225053331512079
 7  9 0.0239075792682171
 7 14 0.0222343245946427
 8  9 0.0224947575431974
 8 10 0.0259331832060178
 8 12 0.0227525834204816
 8 13 0.0223768752560173
 8 14 0.0223839654721248
 9 13 0.0223333187890952
 9 14 0.0233707396802904
10 11 0.0247836632820100
10 12 0.0231195566008868
10 13 0.0237113172691831
10 14 0.0224461979778054
10 15 0.0222144718706271
11 12 0.0359523557525197
11 13 0.0232883288308498
11 15 0.0285710707914430
12 13 0.0221951174734581
12 14 0.0223024273663844
12 15 0.0225769922365633
13 14 0.0237292800085860
13 15 0.0222613790897664
;

proc optmodel;
   num n = 15;
   set NODES = 1..n;
   set EDGES = {i in 1..n-1, j in i+1..n};
   num w {EDGES} init 0;
   read data indata into [i j] w;
   num numGroups init 0;
   set GROUPS = 1..numGroups;
   set NODES_g {GROUPS};
   set <num,num> EDGES_g {GROUPS};
   num groupWeight {g in GROUPS} = sum {<i,j> in EDGES_g[g]} w[i,j];
   for {i in NODES} do;
      numGroups = numGroups + 1;
      NODES_g[numGroups] = {i};
      EDGES_g[numGroups] = {};
   end;
   for {<i,j> in EDGES} do;
      numGroups = numGroups + 1;
      NODES_g[numGroups] = {i,j};
      EDGES_g[numGroups] = {<i,j>};
   end;
   for {<i,j> in EDGES, <(j),k> in EDGES} do;
      numGroups = numGroups + 1;
      NODES_g[numGroups] = {i,j,k};
      EDGES_g[numGroups] = {<i,j>,<i,k>,<j,k>};
   end;

   var IsGroup {GROUPS} binary;
   max TotalWeight = sum {g in GROUPS} groupWeight[g] * IsGroup[g];
   con OneGroupPerNode {i in NODES}:
      sum {g in GROUPS: i in NODES_g[g]} IsGroup[g] = 1;

   solve;
   for {g in GROUPS: IsGroup[g].sol > 0.5} put NODES_g[g];
quit;

---

Whichever approach you use, the optimal objective value for your sample data is $0.3693906073$, and an optimal partition is $$\{ \{1,2,3\}, \{4,5,6\}, \{7,9,14\}, \{8,10,13\}, \{11,12,15\} \}.$$