4
$\begingroup$

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}}
$\endgroup$
2
  • $\begingroup$ Each node contributes 1 no matter which group contains it, so you can just maximize the sum of edge weights and omit the $1, 1+1, 1+1+1$. $\endgroup$
    – RobPratt
    Jun 11 at 13:37
  • $\begingroup$ @RobPratt thanks a lot. What will be an efficient LP formulation for this problem? Also, just one node can form a group. $\endgroup$ Jun 11 at 13:54
11
$\begingroup$

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\} \}.$$

$\endgroup$
16
  • $\begingroup$ thanks a lot. I see that the number of groups is same as the number of nodes. So, the solution will provide the optimal number of groups? $\endgroup$ Jun 11 at 21:13
  • $\begingroup$ I corrected the formulation just now to allow some groups to be empty. $\endgroup$
    – RobPratt
    Jun 11 at 22:03
  • $\begingroup$ you corrected and re-corrected! So, we do not need the additional binary variable that you introduced during the first correction? $\endgroup$ Jun 11 at 23:15
  • $\begingroup$ Yes, the additional binary variable was correct but unnecessary. It was simpler to just remove the lower bound of 1 on the group size. $\endgroup$
    – RobPratt
    Jun 11 at 23:34
  • $\begingroup$ Is is taking too long to get the solution. Can we exploit some intrinsic properties of this model or use any technic to make it faster. I have N=15. $\endgroup$ Jun 12 at 10:22

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.