Formulate and solve a MAXCUT problem

[Issac]

Hi Johan;

I've just started to use YALMIP and want to formulate and solve a SDP relaxation of the MAXCUT problem. The problem can be expressed as

Max < Cn*n , Xn*n>

subject to:

diag(X) = 1n*1 

X is symmetric positive semi-definite

in which C is the (weighted) adjacency matrix of a graph and <p,q> denotes the standard inner product; that means the objective function is really trace (C' X).

For this, I write the following code in matlab (with SDPT3) but I don't know whether it's the correct way to do it or not.

Enter code here...
X=sdpvar(n,n);

F = set (X >= 0);

for i = 1:n

F = F + set (X(i,i) == 1); 

end   

obj= trace(C' * X);

ops=sdpsettings ('solver','sdpt3');

solvesdp(F , -obj , ops);

Appreciate if you let me know about the correctness of the above code.

Isaac

[Johan Löfberg]

Correct. However

1. SET is obsolete
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Set
2. Vectorize
3. Tell YALMIP to interpret as parameterization of primal
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.AutomaticDualization

X=sdpvar(n,n);

F = X >= 0;
F = [F, diag(X)==1];
obj= trace(C' * X);

ops=sdpsettings ('solver','sdpt3','dualize',1);

[Issac]

Thanks Johan;

One thing I see when I run the code is unexpected; the original SDP relaxation of MAXCUT used in graph partitioning begins with the assumption that each xi should be {+1,-1}. But when I solve the problem, off-diagonal of double(X) has all continuous between (-1,+1). So I;d like to ask if there's anything I missed here.

Thanks!

Isaac  

[Johan Löfberg]

That's the whole idea with a relaxation. You solve an intractable problem by solving an optimistic approximation