How to model and solve this optimization problem in CVX?

MIDCP
1

I have a system with 72 nodes.
I have a binary adjacency matrix S of size 72\times 72. If S_{i,j}=1, then node I is adjacent to node j. So, we also have S_{i,j}=S{j,i}. So, S is a binary symmetric matrix.

D is an another matrix of same size. It is the distance matrix. D_{i,j} is the distance between node i and node j, so, D_{i,i}=0.

Now, my target is to form 12 adjacent groups of nodes where we have exactly 6 nodes in each group/cluster. The group elements are adjacent, i.e, every node of a group must be adjacent to at least one of the remaining nodes in that cluster. The group elements should be as close as possible, i.e., the sum of distances needs to be minimize.

Can this problem be modeled in CVX?

Some Thoughts:

If possible can we consider a variable binary integer matrix B\in 72\times 12? So, B_{i,j} defines the association of nodes in a cluster. If B_{i,j}=1, it means that node i is in cluster j. The summation of all the elements in each column is 6.

Let W=S.*D is a weighted adjacent matrix.

Lets say, vector U\in 1\times 12 contains all the summations of distances in a cluster and we can solve a min-max problem as

            Minimize Max U
                W==SD; % (element-wise multiplication)
                U==sum(W B); % (matrix multiplication)
                sum(B)=6*ones(1,12);

But, the question is how to formulate the constraints required to form the clusters? That is each node is a cluster must be adjacent to at least one one of the remaining nodes in that cluster

So, we need some constraint based on the relationship between S and A.

1 Like
2

This forum deals with CVX, not Mathematica. Moreover, formulation of an optimization problem (model) to model your problem of interest is outside the scope of this forum. If you have a mathematical formulation of an optimization problem which would be convex not 'counting" binary or integer restrictions, then you may receive help on this forum getting it into a form which can be handled by CVX;s MIDCP rules.

Anyhow, without looking at your problem very carefully, I strongly suspect that this could be handled by CVX, presuming the solver can solve it within run-time and memory constraints.

3

@Mark_L_Stone,

Thank you very much. In fact I was trying to solve this problem in terms of graph partitioning using Mathematica. Then I failed it. Then I realized like I can instead use CVX to solve it as we can formulate is as a Min-Max optimization problem. Please see my update. I hope you can help me model the last constraint so that we can put it in CVX and solve it. I am stuck with this quite for some time. Are the constraints that I constructed are correct?

4

S and D are input data. Your definition and use of B seems good, and would be declared as
variable B(72,12) binary

You need to add constraint
sum(B,2) == 1 (corrected typo)
so that each node is assigned to only one cluster. This constraint is not implied by the other constraints. Therefore it is needed.

Note that
sum(B)=6*ones(1,12)
can be written more simply as
sum(B,1) == 6. (corrected typo as noted in OP’s post below plus another typo)

I think the constraint that every node must be adjacent to at least one other node in that group (cluster) can be expressed as
sum(S.*repmat(B,1,6),2) >= 1
I leave you to check whether this is correct.

5

Just Typo Correction:

Note that
sum(B)=6*ones(1,12)
can be written more simply as
`sum(B,2) == 6 .

That means, the overall optimization becomes:

Minimize Max U
                W==SD; % (element-wise multiplication)
                U==sum(W B); % (matrix multiplication)
                sum(B,2)==6;
                sum(S.*repmat(B,1,6),2) >= 1
6

Please note I have made additional typo corrections in my previous post, not of all of which are in the current version of your post immediately preceding this post,.

No guarantees this is correct. I have not run it, and actually can not, as I don’t have CVX professional needed to use binary variables. I have not even really checked the correctness of the mathematical logic of this formulation. It’s possible that this formulation makes no sense at all. So I leave it to you to think it through and check it.

cvx_begin
variable B(72,12) binary 
minimize(max(max(D.*repmat(B,1,6))))
sum(B,1) == 6
sum(S.*repmat(B,1,6),2) >= 1
cvx_end
7

Hi Mark,

Here is the error message I am getting…

Error using cvx/max (line 209)
Disciplined convex programming error:
Invalid computation: max( {mixed real affine/complex affine} )

Error in Clustering_Main_Second (line 17)
minimize(max(max(D.*repmat(B,1,6))))

Just to make sure, I put the absolute value of D in the optimization. Then it works, but the result I get is not what we expect. It forms the cluster with non-adjacent nodes.

8

What is the result of norm(imag(D),'fro') . If not exactly zero, then you need to fix the D matrix. CVX will produce error messages even for roundoff level imaginary components for expressiions which CVX needs to be real., It was my assumption that D is a real matrix. If it is not, you need to review the calculations used to create it; did you take square root of a numerically negative number in order to create an entry in D ?

Presuming you do fix it, then as I wrote, I don;t guarantee the correctness of my program, and leave it to you to take it as a starting point to think things through, and fix the program if necessary. If “optimal” nodes returned by CVX are not adjacent, then you need to review the correctness of the logic in the constraint meant to ensure it (my constraint was intended to ensure there is at least one adjacent node in the same group for each node,.

I suggest you start with a small version of the problem, for instance B being 12 by 4, (or even smaller) so that it will be easier to see what is going on, and see the whole B matrix, and he (12 by 12) Hadamard (.* ) products of matrices with repmat matrices. . Once you have that working correctly, then scale up to your actual 72 by 12 problem.

9

Thank you very much. Yes, I will look into it. Anyway, norm(imag(D),'fro') is 0 in my case.

10

If you entered the program in my post, then even though I am not sure it correctly models your problem, it should not produce the error message

Error using cvx/max (line 209)
Disciplined convex programming error:
Invalid computation: max( {mixed real affine/complex affine} )

Error in Clustering_Main_Second (line 17)
minimize(max(max(D.*repmat(B,1,6))))

unless D has at least one non-zero imaginary element (even if it is of magnitude 1e-20, for instance)… I suggest you start a new MATLAB session, create or import S and D matrices, verify that imag(S) and imag(D) have no non-zero imaginary elements of any magnitude (don’t use bank format to examine them), and run my code again.

11

Yes, I understand, I did not have that error message when I replied you last time.