Wolfram言語™

最大カット問題を解く

この例では，バージョン12の新関数のSemidefiniteOptimizationを使ってNP完全最大カット問題の緩和を効率よく解く関数を設定する方法を説明する．

ランダムグラフの最大カットを求める．

グラフのラプラス行列を計算する．

SemidefiniteOptimizationを使って関数を設定する．

ランダムに丸めることでカットを作成する．

カットをハイライトする．