クリーク被覆問題

クリーク被覆問題#

ここでは、JijZeptSolverとJijModelingを用いて、クリーク被覆問題を解く方法を説明します。 この問題は、Lucas, 2014, "Ising formulations of many NP problems"の 6.2. Clique Coverでも触れられています。

クリーク被覆問題とは#

この問題は、与えられたグラフを分割できる、クリーク (完全グラフ)の最少数を求めるというものです。 これはNP完全問題としても知られています。

完全グラフ#

完全グラフとは、グラフ内の2頂点間がすべて辺で結ばれているようなグラフのことです (ただしループや多重辺は含まれません。) 例として、以下のようなものが挙げられます。

先程説明したように、完全グラフの頂点は、その他の全ての頂点と辺で結ばれています。 完全無向グラフ \(G = (V, E)\)は、\({}_V C_2 = \frac{1}{2} V (V-1)\)個の辺を持ちます。 すなわち、辺の数は頂点\(V\)の中から2つを選ぶ組合せの数となります。 完全グラフの辺数からのずれを最小化することで、クリーク被覆問題の数理モデルを記述してみましょう。

数理モデルの構築#

最初に、もし頂点\(v\)が\(n\)番目の部分グラフに含まれるなら1、そうでないなら0となるようなバイナリ変数\(x_{v, n}\)を導入しましょう。

制約: 頂点は必ず1つのクリークに属さなければならない。#

この問題では、各頂点は必ず1つのクリークに含まれる必要があります。

\[ \sum_{n=0}^{N-1} x_{v, n} = 1 \quad (\forall v \in V) \tag{1} \]

目的関数: 完全グラフの辺数からの差を最小化する#

\(n\)番目の部分グラフ\(G (V_n, E_n)\)を考えましょう。 この部分グラフが完全グラフのとき、先程の議論から、この部分グラフの変数は\(\frac{1}{2} V_n (V_n - 1)\)となります。 これに対し、\(n\)番目の部分グラフの辺の数は\(\sum_{(uv) \in E_n} x_{u, n} x_{v, n}\)のように計算できます。 この2つの差が0に近いほど、その部分グラフはクリークに近くなります。 よって、この問題を目的関数は以下のようになります。

\[ \sum_{n=0}^{N-1} \left\{ \frac{1}{2} \left( \sum_{v=0}^{V-1} x_{v, n} \right) \left( \sum_{v=0}^{V-1} x_{v, n} -1\right) - \sum_{(uv) \in E} x_{u, n} x_{v, n} \right\} \tag{2} \]

JijModelingによるモデル化#

次に、JijModelingを用いた実装を示します。 最初に、上述の数理モデルで用いる変数を定義しましょう。

import jijmodeling as jm

problem = jm.Problem('Clique Cover')

# define variables
V = problem.Natural('V')
E = problem.Graph('E')
N = problem.Natural('N')
x = problem.BinaryVar('x', shape=(V, N))

制約#

次に、制約式(1)を実装しましょう。

problem += problem.Constraint('color', lambda v: jm.sum(N, lambda n: x[v, n]) == 1, domain=V)

目的関数#

次に、目的関数式(2)を実装しましょう。

problem += jm.sum(
    N, 
    lambda n: 0.5 * jm.sum(V, lambda v: x[v, n]) * (jm.sum(V, lambda v: x[v, n])-1) - jm.sum(E, lambda e: x[e[0], n]*x[e[1], n]),
)

Jupyter Notebookで、実装された数理モデルを表示してみましょう。

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Clique Cover}\\\displaystyle \min &\displaystyle \sum _{n=0}^{N-1}{\left(0.5\cdot \left(\sum _{v=0}^{V-1}{{x}_{v,n}}\right)\cdot \left(\sum _{v=0}^{V-1}{{x}_{v,n}}-1\right)-\left(\sum _{e\in E}{{x}_{{e}_{0},n}\cdot {x}_{{e}_{1},n}}\right)\right)}\\&\\\text{s.t.}&\\&\begin{aligned} \text{color}&\quad \displaystyle \sum _{n=0}^{N-1}{{x}_{v,n}}=1\quad \forall v\;\text{s.t.}\;v\in \left\{0,\ldots ,V-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V\times N;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\times \mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\times \mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

インスタンスの準備#

Networkxを用いて、グラフを準備しましょう。

import networkx as nx

# set the number of colors
inst_N = 3
# set empty graph
inst_G = nx.Graph()
# add edges
inst_E = [[0, 1], [1, 2], [0, 2], 
            [3, 4], [4, 5], [5, 6], [3, 6], [3, 5], [4, 6], 
            [7, 8], [8, 9], [7, 9], 
            [1, 3], [2, 6], [5, 7], [5, 9]]
inst_G.add_edges_from(inst_E)
# get the number of nodes
inst_V = list(inst_G.nodes)
num_V = len(inst_V)
instance_data = {'N': inst_N, 'V': num_V, 'E': inst_E}

準備されたグラフを可視化してみましょう。

import matplotlib.pyplot as plt

nx.draw_networkx(inst_G, with_labels=True)
plt.show()
../_images/01d91c3ad817a823c861e61d6e659edcc51bca5f6aee87f0825370f24947118a.png

このグラフは、(0, 1, 2), (3, 4, 5, 6), (7, 8, 9)の3つのクリークからなることがわかります。 次は、JijZeptSolverで解いてみましょう。

JijZeptSolverで解く#

この問題を、jijzept_solverで解きましょう。

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

最後に、得られた解を可視化しましょう。

df = solution.decision_variables_df
x_indices = df[df["value"]==1.0]["subscripts"]
# initialize vertex color list
node_colors = [-1] * len(x_indices)
# set color list for visualization
cmap = plt.get_cmap("tab10")
colorlist = [cmap(i) for i in range(inst_N)]
# set vertex color list
for i, j in x_indices:
    node_colors[i] = colorlist[j]
# make figure
nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)
plt.show()
../_images/145b19a1a69417bc0e10621a6b0b7146661adbf25e7ce23c850085606d22d1ef.png

予想通り、JijZeptSolverによりグラフを3つのクリークに分割することができました。

目次