最大クライブ問題
無向グラフ $G=(V,E)$ に対し、最大クラン問題とは、$S\subseteq V$ において、$S$ 内の異なる頂点ペアがすべて $E$ の辺で接続されるような最大部分集合 $S$ を求める問題である。
頂点を $0,1,\ldots,n−1$ とラベル付けすると仮定する。 $n$ 個の二値変数 $x_0, x_1, \ldots, x_{n-1}$ を導入する。 ここで $x_i=1$ は、頂点 $i$ が $S$ に属する場合にのみ真となる（$0\leq i\leq n−1$）。 すると、$S$ のサイズは次式で与えられる
\[\begin{aligned} \text{目的関数} &= \sum_{i=0}^{n-1}x_i. \end{aligned}\]$S$が完全グラフ（クワイク）であるためには、選ばれたノードのすべてのペアが辺で結ばれている必要がある。 等価的に、ノードのペア $i$ と $j$ について、 $(i,j)\not\in E$ ならば、$i$ と $j$ の両方を同時に選ぶことはできない。 これは以下の制約で表現できる：
\[\begin{aligned} \text{制約条件} &= \sum_{(i,j)\not\in E}x_ix_j \end{aligned}\]実現可能なクランは $constraint=0$ を満たす。 したがって、以下の QUBO 形式の目的関数 $f$（最小化対象）が得られる：
\[\begin{aligned} f &= -\text{目的関数}+2\times \text{制約条件} \end{aligned}\]ここで 2 はペナルティ係数である。
$f$を最小化する最適解は最大クランクに対応し、目的関数値は選択されたノードの数に等しい。
最大クワイク問題に対する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, 12}, {4, 14},
{5, 8}, {6, 8}, {6, 12}, {6, 14}, {7, 14}, {7, 15},
{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();
std::vector<std::vector<bool>> adj(N, std::vector<bool>(N, false));
for (auto [u, v] : edges) {
adj[u][v] = adj[v][u] = true;
}
auto x = qbpp::var("x", N);
auto objective = qbpp::sum(x);
auto constraint = qbpp::Expr(0);
for (size_t i = 0; i < N; ++i) {
for (size_t j = i + 1; j < N; ++j) {
if (!adj[i][j]) {
constraint += x[i] * x[j];
}
}
}
auto f = -objective + N * 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).color(sol(x[i])));
}
for (size_t i = 0; i < M; ++i) {
auto edge = qbpp::graph::Edge(edges[i].first, edges[i].second);
if (sol(x[edges[i].first]) && sol(x[edges[i].second])) {
edge.color(1).penwidth(2.0);
}
graph.add_edge(edge);
}
graph.write("maxclique.svg");
}
辺リストから edgesから隣接行列 adjを構築する。これにより、任意のノードペアがグラフ内で辺を形成するかどうかを判定できる。
ベクトル x の N = 16 二値変数のベクトル objective, constraint、および f は上記のQUBO形式に従って構築される。
特に、 adj[i][j] が偽の場合、二次項 x[i] * x[j] が constraint.
その後、完全探索ソルバーを用いて、 fを最小化する最適解を求め、その解は solに格納される。 objective および constraint は sol で評価された値が印刷される。
A qbpp::graph::GraphDrawer オブジェクト graph が作成され、選択されたクランのノードとクランのエッジが強調表示される。
このプログラムは以下の出力を生成する:
objective = 4
constraint = 0
この出力から、制約を破らずに4ノードの最大クワイクを得ます。
結果は以下のように可視化されます: maxclique.svg 次のように可視化されます:
