Max-Cut Problem
The max-cut problem determines a subset 
of the vertices 
of a graph, for which the sum of the weights 
of the edges that cross from 
to its complement 
is maximized.
This example demonstrates how SemidefiniteOptimization may be used to set up a function that efficiently solves a relaxation of the NP-complete max-cut problem.
Suppose that 
has 
vertices so that they can be described by an index 
. Let 
be a vector with components 
for 
and 
for 
so that 
is nonzero (=2) only if 
and 
. Thus the max-cut is found by maximizing 
, where 
. The objective can be rewritten as:
... where 
is the Laplacian matrix of the graph and 
is the weighted adjacency matrix.
For smaller cases, the max-cut problem can be solved exactly, but this is impractical for larger graphs since in general the problem has NP-complete complexity.
The problem minimizes 
, where 
is a symmetric rank-1 positive semidefinite matrix, with 
for each 
, equivalent to 
, where 
is the matrix with 
at the 
diagonal position and 0 everywhere else.
To make the solution practical, solve a relaxed problem where the rank-1 condition is eliminated so that it only requires 
.
The semidefinite problem in dual form is given by
It is solved using SemidefiniteOptimization[c, {a0, a1, …, ak}, {"DualMaximizer" }].
For the solution 
of the relaxed problem, a cut is constructed by randomized rounding: decompose 
, let 
be a uniformly distributed random vector of the unit norm and let 
. For demonstration, a function is defined that shows the relaxed value, the rounded value and the graph, with the vertices in 
shown in red.
Find an approximate max cut using the previously shown procedure, and compare with the exact result.
Find the max cut for a grid graph.
Find the max cut for a random graph.
Compare timings for the relaxed and exact algorithms for a Peterson graph.
