What() is:bad allocation with CVX SDP on Matlab

I’m given 2016 elements, and I take these elements and create a graph with the edges determine by the distance of the elements. If the distance of two elements is precisely 2, I give a edge between them. Now, I try to estimate the number of elements in the maximum independent set of the graph using the Lovasz Theta Number. However, the Program runs about 2 hours and send back the following:

Unexpected Standard exception from MEX file.
What() is:bad allocation

I see that this is due to a memory issue, but how can I modify the program so it is able to solve this graph.

The following is my code:

close;clear all;clc
space = xlsread(‘D:\Code\space.xlsx’);
distmat = zeros(2016);
for i=1:2016
for j=1:2016
distmat(2016*(i-1)+j) = sum(abs(space(i,:)-space(j,:)));
cvx_begin SDP
variable B(2016,2016) symmetric
maximize (sum(sum(B)))
subject to
B >= 0;
for i=1:2016
for j=1:2016
if distmat(i,j)==2

Any help would be greatly appreciated!

Try on a computer with more RAM.

My computer has RAM 24GB, and the following is what I get in the command line:

Calling SDPT3 4.0: 2033136 variables, 44353 equality constraints

num. of constraints = 44353
dim. of sdp var = 2016, num. of sdp blk = 1

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|8.4e+05|4.5e+01|6.8e+09|-1.683470e+06 0.000000e+00| 0:0:11| spchol 1 1
1|0.973|1.000|2.3e+04|5.6e-03|1.8e+08|-3.105473e+06 -4.034815e+03| 0:0:29| chol 1 1
2|0.989|1.000|2.6e+02|1.7e-03|2.0e+06|-3.461663e+04 -4.035006e+03| 0:5:09|------------------------------------------------------------
Status: Error
Optimal value (cvx_optval): NaN

I don’t if this is possible to answer, but may I ask how much RAM do I need to finish the program? Sorry if this is a stupid question.

Interesting. Your SDPT3 log seems to suggest that you have around 44000 edges, so pretty sparse for a graph on 2016 vertices, is that correct?

I generated a random graph with 2016 vertices and 44000 edges and MOSEK went through the first few iterations showing the usage of 5% of the 512GB RAM machine where I’m running this, so around 25GB. So it is possible you are pretty close. Maybe if you turn multithreading off it will fit, you could try that.

The complexity and memory will grow very quickly as you increase the number of edges, since that translates directly on the number of linear constraints involving semidefinite terms. I don’t think computing the theta number of a general graph on 2016 vertices is within reach at all.

Thanks a million, it helps a lot! But it is right that the result is rather loose by using theta number, I will have to learn more! Thanks again!