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.