How can I model this objective and constraint in CVX?

MIDCP
1

I have a hard time expressing this in CVX.
It is the third solution proposed here https://or.stackexchange.com/questions/6428/how-to-partition-a-graph-with-optimal-number-of-groups

I could solve the first two with CVX with MOSEK, but could not manage to implement the third solution.

It corresponds to finding optimal groups from a graph. The graph has N nodes, and the edges connecting two nodes has a weight.

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

\sum_{g\in G:\ i\in N_g} u_g = 1 \text{ for all } i

Any suggestion!

Let M=|G| be the cardinality of G.

variable u(M)

N_g is of varying sizes, I can put the index of the nodes in a group by defining a cell structure.

 N_Matrix=cell(M,1);
 for m=1:M
      cell{m}=indexes of the nodes in group m
 end

I am not sure how should I express E so that I can implement in CVX…

2

It appears that E_g is input data to the optimization problem, which you somehow figure out how to compute, independent of anyyhing going on in CVX (variables or expressions). To use that in CVX, yu can then index the elements of summation by the members of E_g, or use any MATLAB logic within a for loop in order to sum over the correct terms. That is no different than how you would evaluate the sum if the CVX variables were instead MATLAB double precision floats. If you need help generating E_g, which really has nothing to do with CVX, I suggest you post a comment at the linked answer requesting the answer author provide assistance.