最大マッチング問題
無向グラフにおけるマッチングとは、どの2つの辺も共通の頂点を持たない辺の集合である。 無向グラフ $G=(V,E)$ が与えられたとき、最大マッチング問題とは、辺の数が最大となるマッチング $S \subseteq E$ を見つけることを目的とする。
グラフが $n$ 個の頂点と $m$ 個の辺を持ち、辺が $0,1,\ldots,m-1$ でラベル付けされていると仮定する。 二値変数 $x_0, x_1, \ldots, x_{m-1}$ を導入する。ここで $x_i=1$ となるのは、辺 $i$ が選択される（すなわち $S$ に属する）場合に限る（$0\le i\le m-1$）。 目的は選択される辺の数を最大化することである：
\[\begin{aligned} \text{目的関数} &= \sum_{i=0}^{m-1} x_i . \end{aligned}\]マッチング条件を強制するため、共通の頂点を持つ選択された辺のペアに対してペナルティを課す。 $\mathcal{P}$ を共通の終点を持つ異なる辺の無順序なペア $(e_1,e_2)$ の集合とする。 このとき、選択された辺がマッチングを形成する場合に限り、以下のペナルティは値 $0$ となる：
\[\begin{aligned} \text{制約} &= \sum_{\{e_1,e_2\}\in \mathcal{P}} x_{e_1}x_{e_2}. \end{aligned}\]目的関数とペナルティを組み合わせて、次のようにQUBO式$f$を構築する：
\[\begin{aligned} f &= -\text{目的関数} + 2 \times \text{制約関数}. \end{aligned}\]ここで、ペナルティ項に2を乗じることで、マッチング制約違反が目的関数の増加よりもコストが高くなるようにしている。 したがって、$f$を最小化する割当ては、グラフ$G$の最大マッチングに対応する。
最大マッチングのためのQUBO++プログラム
上記の定式化に基づき、以下のQUBO++プログラムは16ノードグラフに対するQUBO式$f$を構築し、Exhaustive Solverを用いて解く
#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}};
const size_t M = edges.size();
auto x = qbpp::var("x", M);
auto objective = qbpp::sum(x);
auto constraint = qbpp::toExpr(0);
for (size_t i = 0; i < M; ++i) {
for (size_t j = i + 1; j < M; ++j) {
if (edges[i].first == edges[j].first ||
edges[i].first == edges[j].second ||
edges[i].second == edges[j].first ||
edges[i].second == edges[j].second) {
constraint += x[i] * x[j];
}
}
}
auto f = -objective + 2 * constraint;
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));
}
for (size_t i = 0; i < M; ++i) {
auto edge = qbpp::graph::Edge(edges[i].first, edges[i].second);
if (sol(x[i])) {
edge.color(1).penwidth(2.0);
}
graph.add_edge(edge);
}
graph.write("maxmatching.svg");
}
このプログラムは式 objective, constraint, および f、ここで f は否定された objective の否定値にペナルティ項を加えたものです。
完全探索ソルバーは fを最小化し、最適な割り当てを sol.
解を可視化するため、 GraphDrawer オブジェクト graph が作成され、ノードとエッジで構成される。
この可視化では、$S$内の選択されたエッジ（すなわち、$x_i=1$であるエッジ$i$）が強調表示される。
生成されたグラフはレンダリングされ、ファイル maxmatching.svg:
