https://www.topcoder.com/challenges/30084839
重み付き最大カット問題は、ある重み付きグラフが与えられるので、ノードを2つのグループに分割するという問題です。このとき、あるエッジがノード$(i,j)$を結び、その重みが$d_{i,j}$であるとき、ノード$(i,j)$が異なるグループに属していればスコア$d_{i,j}$を得ます。
この問題はデジタルアニーラのLarning Challengeですので、解法の概要およびコードはTutorialに記載されています(コンテスト期間中は、bouild_max_cut_ruleの実装だけは公開されていませんでした。)。この記事では、Tutorialの内容について行間を埋める形で解説することを目指します。
前回、前々回と同様に、値を最小化することでMax Cut問題が解けるようなquadratic polynomialを構成することを目指します。この問題は非常にシンプルで、スコアが最大となる場合にエネルギー最小となるような関数として $$-\sum_{(i,j)\; is\; an\; edge} d_{i,j} \left( x_i-x_j \right)^2$$ をとることができて、これをそのまま最小化すればよいです。ここで、$x_i$は$i$番目のノードがどちらのグループに属しているかを表しています。
よって、 $$H=-\sum_{(i,j)\; is\; an\; edge} d_{i,j} \left( x_i-x_j \right)^2$$ が最小になるような$x_i$を見つけることで、重み付き最大カット問題を解くことができます。これで、重み付き最大カット問題をデジタルアニーラで解ける形に変換することができました。
Tutorialに載っているので、割愛。