Clique Cover Problem#

Here we show how to solve the clique cover problem using OpenJij, JijModeling, and JijModeling Transpiler. This problem is also mentioned in 6.2. Clique Cover in Lucas, 2014, “Ising formulations of many NP problems”.

Overview of the Clique Cover Problem#

The clique covering problem is to determine whether, given a graph and an integer nn, the graph can be partitioned into nn cliques (complete graphs).

Complete Graph#

A complete graph is a graph whose two vertices are all adjacent to each other (not including loops or multiple edges). We show two examples below.

As mentioned, a vertex in a complete graph is adjacent to all other vertices. A complete undirected graph G=(V,E)G = (V, E) has VC2=12V(V1){}_V C_2 = \frac{1}{2} V(V-1) edges, which shows that the number of edges is equal to the number of combinations choosing two vertices from VV. Based on minimizing the difference in the number of edges from a complete graph, we describe a mathematical model for the clique cover problem.

Binary Variable#

We introduce a binary variable xv,nx_{v, n} such that xv,nx_{v, n} is 1 if the vertex vv belongs to the nnth clique and 0 otherwise.

Constraint#

Each vertex can belong to only one clique, meaning that the graph is divided into NN cliques:

(1)#n=0N1xv,n=1(vV) \sum_{n=0}^{N-1} x_{v, n} = 1 \quad (\forall v \in V)

Objective Function#

Let us consider the nnth subgraph G(Vn,En)G (V_n, E_n). The number of vertices is Vn=vxv,nV_n = \sum_v x_{v,n}. If this subgraph is complete, the number of edges of this subgraph is 12Vn(Vn1)\frac{1}{2} V_n (V_n -1) from the previous discussion. The number of edges can actually be written as (uv)Enxu,nxv,n\sum_{(uv) \in E_n} x_{u, n} x_{v, n}. The subgraph GG is neatly divided into cliques when the difference between these two approaches is zero. Therefore, we set the objective function as follows:

(2)#obj=n=0N1{12(v=0V1xv,n)(v=0V1xv,n1)(uv)Exu,nxv,n} \mathbf{obj} = \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\}

Modeling by JijModeling#

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

Variables#

Let us define the variables used in expressions (1) and (2) as follows:

import jijmodeling as jm

# define variables
V = jm.Placeholder('V')
E = jm.Placeholder('E', dim=2)
N = jm.Placeholder('N')
x = jm.Binary('x', shape=(V, N))
n = jm.Element('n', (0, N))
v = jm.Element('v', (0, V))
e = jm.Element('e', E)

V=jm.Placeholder('V') defines the number of vertices in the graph and E=jm.Placeholder('E', dim=2) defines the graph’s edge set. N=jm.Placeholder('N') determines how many cliques the graph is divided into, and V, N is used to define the binary variable xv,nx_{v, n} as x=jm.Binary('x', shape=(V, N)). n, v is the variable used to index the binary variable, and e is the variable for the edge. e[0], e[1] are the vertices located at both ends of edge e, which makes (uv)=(e[0]e[1])(uv) = (e[0] e[1]).

Constraints#

Let us implement the constraint in expression (1).

# set problem
problem = jm.Problem('Clique Cover')
# set one-hot constraint: each vertex has only one color
problem += jm.Constraint('color', x[v, :]==1, forall=v)

x[v, :] implements Sum(n, x[v, n]) in a concise way.

Objective Function#

Let us implement the objective function of expression (2).

# set objective function: minimize the difference in the number of edges from complete graph
clique = x[:, n] * (x[:, n]-1) / 2
num_e = jm.Sum(e, x[e[0], n]*x[e[1], n])
problem += jm.Sum(n, clique-num_e)
problem
Problem: Clique Coverminn=0N1(iˉ0=0V1xiˉ0,n(iˉ0=0V1xiˉ0,n1)2eExe0,nxe1,n)s.t.color:iˉ1=0N1xv,iˉ1=1, v{0,,V1}xi0,i1{0,1}\begin{alignat*}{4}\text{Problem} & \text{: Clique Cover} \\\min & \quad \sum_{ n = 0 }^{ N - 1 } \left( \frac{ \sum_{ \bar{i}_{0} = 0 }^{ V - 1 } x_{\bar{i}_{0},n} \cdot \left( \sum_{ \bar{i}_{0} = 0 }^{ V - 1 } x_{\bar{i}_{0},n} - 1 \right) }{ 2 } - \sum_{ e \in E } x_{e_{0},n} \cdot x_{e_{1},n} \right) \\\text{s.t.} & \\& \text{color} :\\ &\quad \quad \sum_{ \bar{i}_{1} = 0 }^{ N - 1 } x_{v,\bar{i}_{1}} = 1,\ \forall v \in \left\{ 0 ,\ldots , V - 1 \right\} \\[8pt]& x_{i_{0},i_{1}} \in \{0, 1\}\end{alignat*}

With clique, we calculate the number of edges if the vertex had created a clique. The next num_e is the calculated number of edges that the vertex has. Finally, the sum of the differences is added as the objective function.

Instance#

Here we prepare a graph using 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}

The graph set up by this instance is as follows.

import matplotlib.pyplot as plt

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

This graph consists of three cliques (0, 1, 2), (3, 4, 5, 6), and(7, 8, 9).

Undetermined Multiplier#

This problem has one constraint, and we need to set the weight of that constraint. We will set it to match the name we gave in the Constraint part earlier using a dictionary type.

# set multipliers
lam1 = 1.1
multipliers = {'color': lam1}

Conversion to PyQUBO by JijModeling Transpiler#

JijModeling has executed all the implementations so far. By converting this to PyQUBO, it is possible to perform combinatorial optimization calculations using OpenJij and other solvers.

from jijmodeling.transpiler.pyqubo import to_pyqubo

# convert to pyqubo
pyq_model, pyq_chache = to_pyqubo(problem, instance_data, {})
qubo, bias = pyq_model.compile().to_qubo(feed_dict=multipliers)

The PyQUBO model is created by to_pyqubo with the problem created by JijModeling and the instance_data we set to a value as arguments. Next, we compile it into a QUBO model that can be computed by OpenJij or other solver.

Optimization by OpenJij#

This time, we will use OpenJij’s simulated annealing to solve the optimization problem. We set the SASampler and input the QUBO into that sampler to get the result of the calculation.

import openjij as oj

# set sampler
sampler = oj.SASampler()
# solve problem
response = sampler.sample_qubo(qubo, num_reads=100)

Decoding and Displaying the Solution#

Decode the returned results to facilitate analysis.

# decode solution
result = pyq_chache.decode(response)

From the result thus obtained, let us visualize the graph. By using result.feasible(), only feasible solutions can be extracted. From here, the process of coloring the vertices for each clique is performed.

# extract feasible solution
feasible = result.feasible()
if feasible.evaluation.objective == []:
    print('No feasible solution found ...')
else:
    print("Objective: "+str(feasible.evaluation.objective[0]))
    # get indices of x = 1
    indices, _, _ = feasible.record.solution['x'][0]
    # get vertex number and color
    vertices, colors = indices
    # sort lists by vertex number
    zip_lists = zip(vertices, colors)
    zip_sort = sorted(zip_lists)
    sorted_vertices, sorted_colors = zip(*zip_sort)
    # initialize vertex color list
    node_colors = [-1] * len(vertices)
    # set color list for visualization
    colorlist = ['gold', 'violet', 'limegreen']    
    # set vertex color list
    for i, j in zip(sorted_vertices, sorted_colors):
        node_colors[i] = colorlist[j]
    # make figure
    fig = plt.figure()
    nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)
    plt.show()
Objective: 0.0
../../../_images/clique_cover_24_1.png

It is correctly divided into cliques. We recommend you try more complex graphs.