# solving max cut problem on a huge graph (500 x 500) using Semidefinite Programming with CVXOPT

So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward relaxation. $W$ is the weight matrix, $X = u u^T$ where $u$ is the original variables.

$$\max < (I-W),X>$$ $$s.t. X_{ii} = 1, \forall i$$ $$X \succeq 0$$

Problem is:

The solver I am using is CVXOPT, for which I have to convert X into a REALLY long variable, and for CVXOPT I have to paraphrase the constraint into huge matrices (largest ~ 250000 * 125250, but sparse), and load them into the cvxopt.solver.sdp(), but at this line python simply gives up and crashes (jupyter notebook says the kernel has died). I have used CVXOPT's sparse matrix feature for the massive constraint matrices (cost vector must be dense), and it's still not working out.

So my question is: is there any way to work around this? I'm open to anything, rephrasing the problem, using a different solver, or maybe just write the damped newton method for log barrier method myself. I am contemplating about CVXPY, but seeing that it uses CVXOPT as one of its solvers, I don't think I want to waste my time if it's gonna come out the same, and similar reason for writing my own program.

• When you say 500*500 graph, do you mean the graph has 500 vertices? – Juho Feb 28 '18 at 7:12
• This seems more appropriate for Computational Science. – Yuval Filmus Feb 28 '18 at 7:56
• yeah sorry, I meant 500 vertices (500*500 adj matrix) – Donnie Feb 28 '18 at 15:48