Graph Coloring Problem#

Here we show how to solve the graph coloring problem using OpenJij, JijModeling, and JijModeling Transpiler. This problem is also mentioned in 6.1. Graph Coloring in Lucas, 2014, “Ising formulations of many NP problems”.

Overview of the Graph Coloring Problem#

In a graph coloring problem, we color vertices on a given graph differently when they are on the same edge. This problem is one of the famous NP-complete problems.

Example#

Consider an undirected graph with 6 vertices and some edges as shown below.

We can color this graph in three colors as follows:

No edge connects two vertices of the same color exist.

Generalizing the Problem#

Now let us generalize the problem and express it in a mathematical model. Consider an undirected graph G=(V,E)G = (V, E) with NN colors so that vertices connected by edges do not overlap. We consider coloring an undirected graph G=(V,E)G=(V, E) with NN colors, and introduce variables xv,nx_{v, n} which are 1 if vertex vv is colored with nn and 0 otherwise.

Constraint#

Vertices must be painted with one color, meaning that it is not allowed to paint one vertex with two colors.

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

Objective Function#

The problem setup for the graph coloring problem requires that the vertices at both ends of every edge be painted with a different color. This can be expressed as:

(2)#minn=0N1(uv)Exu,nxv,n \min \quad \sum_{n=0}^{N-1} \sum_{(uv) \in E} x_{u, n} x_{v, n}

where EE is a set of edges on graph GG.

xu,nx_{u,n}

xv,nx_{v,n}

xu,nxv,nx_{u,n}x_{v,n}

0

0

0

0

0

0

1

0

0

1

1

1

Since xu,n=1x_{u,n}=1 if vertex uu is colored by nn as defined above, xu,nxv,n=1x_{u,n}x_{v,n}=1 in the table above only when both xu,nx_{u,n} and xv,nx_{v,n} are 1, and 0 otherwise. When two vertices on every edge have different colors, the value of this objective function is 0. Therefore, this objective function is an indicator of the degree to which graph coloring has been achieved.

Modeling by JijModeling#

Variables#

Let us define the variables used in equations (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('i', (0, N))
v = jm.Element('v', (0, V))
e = jm.Element('e', E)

V=jm.Placeholder('V') represents the number of vertices. We denote E=jm.Placeholder('E', dim=2) a set of edges. N is the number of colors. We define a two-dimensional list of binary variables x=jm.Binary('x', shape=(V, N)), and we set the subscripts n and v used in the mathematical model. e represents the variable for edges. e[0] and e[1] mean the vertex uu and vv on the edge, respectively.

Constraint#

Let us implement the constraint in equation (1).

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

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

Objective Function#

Next, we implement the objective function of equation (2). We write ne\sum_n \sum_e as Sum([n, e], ...). JijModeling easily formulates the summation over nodes in edges.

# set objective function: minimize edges whose vertices connected by edges are the same color
sum_list = [n, e]
problem += jm.Sum(sum_list, x[e[0], n]*x[e[1], n])
problem
Problem: Graph Coloringmini=0N1eExe0,ixe1,is.t.one-color:iˉ1=0N1xv,iˉ1=1, v{0,,V1}xi0,i1{0,1}\begin{alignat*}{4}\text{Problem} & \text{: Graph Coloring} \\\min & \quad \sum_{ i = 0 }^{ N - 1 } \sum_{ e \in E } x_{e_{0},i} \cdot x_{e_{1},i} \\\text{s.t.} & \\& \text{one-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*}

Instance#

Here we create a random graph with 12 vertices.

# set the number of vertices
inst_V = 12
# set the number of colors
inst_N = 4
# create a random graph
inst_G = nx.gnp_random_graph(inst_V, 0.4)
# get information of edges
inst_E = [list(edge) for edge in inst_G.edges]
instance_data = {'V': inst_V, 'N': inst_N, 'E': inst_E, 'G': inst_G}
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[4], line 6
      4 inst_N = 4
      5 # create a random graph
----> 6 inst_G = nx.gnp_random_graph(inst_V, 0.4)
      7 # get information of edges
      8 inst_E = [list(edge) for edge in inst_G.edges]

NameError: name 'nx' is not defined

In this code, the number of vertices in the graph and the number of colors are 12 and 4, respectively.

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.0
multipliers = {'one-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(num_reads=100)
# solve problem
response = sampler.sample_qubo(qubo)

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. We prepare a graph using NetworkX.

import matplotlib.pyplot as plt
# get indices of x = 1
indices, _, _ = result.lowest().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', 'darkorange']
# 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(instance_data['G'], node_color=node_colors, with_labels=True)
../../../_images/graph_coloring_21_0.png