最大カット問題
無向グラフ $G=(V,E)$ が与えられたとき、最大切断問題とは、頂点集合 $V$ を二つの互いに素な部分集合 $S$ と $\overline{S}$ に分割し、$S$ に一方の端点を持ち、$\overline{S}$ に他方の端点を持つ辺の数を最大化することを目的とする。
頂点に $0,1,\ldots,n-1$ のラベルが付与されていると仮定する。 二値変数 $x_0, x_1, \ldots, x_{n-1}$ を導入する。ここで $x_i=1$ とは、頂点 $i$ が $S$ に属する場合（$0\le i\le n-1$）に限り成立する。 すると、切断 $(S,\overline{S})$ を横切る辺の数は次式で与えられる
\[\begin{aligned} \text{目的関数} &= \sum_{(i,j)\in E}\Bigl(x_i(1-x_j) + (1-x_i)x_j\Bigr). \end{aligned}\]QUBO問題は目的関数の最小化を目的とするため、目的関数を否定することでQUBO表現$f$を得る：
\[\begin{aligned} f &= -\,\text{目的関数}. \end{aligned}\]$f$を最小化する最適割当ては、グラフ$G$の最大カットに対応する。 さらに、$\text{目的関数}$の値は、集合$S$と集合$\overline{S}$を横切る辺の数に等しい。
MAX-CUT問題のためのQUBO++プログラム
上記の定式化に基づき、以下のQUBO++プログラムは16ノードグラフに対するQUBO表現$f$を構築し、完全探索ソルバーを用いて解く：
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
#include "qbpp_graph.hpp"
int main() {
const size_t N = 16;
std::vector<std::pair<size_t, size_t>> edges = {
{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7},
{3, 13}, {4, 6}, {4, 7}, {4, 14}, {5, 8}, {6, 8}, {6, 12},
{6, 14}, {7, 14}, {8, 9}, {9, 10}, {9, 12}, {10, 11}, {10, 12},
{11, 13}, {11, 15}, {12, 14}, {12, 15}, {13, 15}, {14, 15}};
auto x = qbpp::var("x", N);
auto objective = qbpp::toExpr(0);
for (const auto& edge : edges) {
objective += x[edge.first] * (1 - x[edge.second]) +
(1 - x[edge.first]) * x[edge.second];
}
auto f = -objective;
f.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
auto sol = solver.search();
std::cout << "objective = " << objective(sol) << std::endl;
qbpp::graph::GraphDrawer graph;
for (size_t i = 0; i < N; ++i) {
graph.add_node(qbpp::graph::Node(i).color(sol(x[i])));
}
for (const auto& e : edges) {
auto edge = qbpp::graph::Edge(e.first, e.second);
if (sol(x[e.first]) != sol(x[e.second])) {
edge.color(1).penwidth(2.0);
}
graph.add_edge(edge);
}
graph.write("maxcut.svg");
}
このプログラムは次の式を生成する objective および fここで f は objectiveの否定である。
完全探索ソルバーは fを最小化し、最適な割り当てを sol.
解を可視化するために、 GraphDrawer オブジェクト graph が作成され、ノードとエッジで構成される。
この可視化では、S 内のノード $i$（すなわち $x_i=1$ であるノード）が着色され、カットを横切るエッジが強調表示される。
このプログラムは以下の出力を生成する:
objective = 22
結果のグラフはレンダリングされ、ファイル maxcut.svg:
