最大カット問題¶
無向グラフ \(G=(V,E)\) が与えられたとき,最大カット問題は,ノード集合 \(V\) を2つの互いに素な部分集合 \(S\) と \(\overline{S}\) に分割し,一方の端点が \(S\) に,他方の端点が \(\overline{S}\) にある \(E\) の辺の数を最大化することを目的とします.
ノードに \(0,1,\ldots,n-1\) のラベルが付いているとします. \(n\) 個のバイナリ変数 \(x_0, x_1, \ldots, x_{n-1}\) を導入し,\(x_i=1\) はノード \(i\) が \(S\) に属することを表します (\(0\le i\le n-1\)). すると,カット \((S,\overline{S})\) を横断する辺の数は以下で与えられます：
QUBO 問題は目的関数を最小化するため,目的関数を符号反転して QUBO 式 \(f\) を得ます：
\(f\) を最小化する最適な割り当ては \(G\) の最大カットに対応します. また,\(\text{objective}\) の値は \(S\) と \(\overline{S}\) の間を横断する辺の数に等しくなります.
最大カット問題の Hi-QUBO プログラム
上記の定式化に基づき,以下の Hi-QUBO プログラムは 16 ノードのグラフに対する QUBO 式 \(f\) を構築し,Exhaustive Solver を用いて解きます：
#include <qbpp/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] * ~x[edge.second] +
~x[edge.first] * x[edge.second];
}
auto f = -objective;
f.simplify_as_binary();
auto solver = qbpp::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 の符号反転です.
Exhaustive Solver が f を最小化し,最適な割り当てが sol に格納されます.
解を可視化するために,GraphDrawer オブジェクト graph を作成し,ノードと辺を追加します.
この可視化では,\(S\) に属するノード \(i\)（つまり \(x_i=1\) のノード）が着色され,カットを横断する辺が強調表示されます.
このプログラムの出力は以下の通りです：
結果のグラフは描画され,ファイル maxcut.svg に保存されます：
無向グラフ \(G=(V,E)\) が与えられたとき,最大カット問題は,ノード集合 \(V\) を2つの互いに素な部分集合 \(S\) と \(\overline{S}\) に分割し,一方の端点が \(S\) に,他方が \(\overline{S}\) に属する \(E\) 中の辺の数を最大化することを目的とします.
ノードは \(0,1,\ldots,n-1\) とラベル付けされているとします. \(n\) 個のバイナリ変数 \(x_0, x_1, \ldots, x_{n-1}\) を導入し,\(x_i=1\) はノード \(i\) が \(S\) に属する場合にのみ成り立ちます（\(0\le i\le n-1\)）. このとき,カット \((S,\overline{S})\) を横切る辺の数は次のように与えられます：
QUBO 問題は目的関数を最小化することを目指すため,目的関数を符号反転して QUBO 式 \(f\) を得ます：
\(f\) を最小化する最適な割り当ては,\(G\) の最大カットに対応します.
Max-Cut 問題の PyQBPP プログラム
import pyqbpp as qbpp
N = 16
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)]
x = qbpp.var("x", shape=N)
objective = 0
for u, v in edges:
objective += x[u] * ~x[v] + ~x[u] * x[v]
f = -objective
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()
print(f"objective = {sol(objective)}")
print("S:", end="")
for i in range(N):
if sol(x[i]) == 1:
print(f" {i}", end="")
print()
このプログラムは式 objective と f を作成します.f は objective の符号反転です.
Exhaustive Solver が f を最小化し,最適な割り当てが sol に格納されます.
このプログラムは以下の出力を生成します：
objective = 22
S: 1 5 6 7 9 10 13 15
matplotlib による可視化
以下のコードは matplotlib と networkx を用いて Max-Cut の解を可視化します：
import matplotlib.pyplot as plt
import networkx as nx
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
pos = nx.spring_layout(G, seed=42)
colors = ["#e74c3c" if sol(x[i]) == 1 else "#3498db" for i in range(N)]
edge_colors = ["#e74c3c" if sol(x[u]) != sol(x[v]) else "#cccccc"
for u, v in edges]
edge_widths = [2.5 if sol(x[u]) != sol(x[v]) else 1.0
for u, v in edges]
nx.draw(G, pos, with_labels=True, node_color=colors, node_size=400,
font_size=9, edge_color=edge_colors, width=edge_widths)
plt.title("Max-Cut")
plt.savefig("maxcut.png", dpi=150, bbox_inches="tight")
plt.show()
2つの分割は赤と青で表示されます.カット辺（分割を横切る辺）は赤でハイライトされます.