Solve Max-Cut Problem
This example demonstrates how the new SemidefiniteOptimization in Version 12 may be used to set up a function that efficiently solves a relaxation of the NP-complete max-cut problem.
Find the maximum cut for a random graph.
Compute the Laplacian matrix of the graph.
Use SemidefiniteOptimization to set up a function.
Construct a cut by randomized rounding.
Highlight the cut.