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)$ with $N$ colors so that vertices connected by edges do not overlap. We consider coloring an undirected graph $G=(V, E)$ with $N$ colors, and introduce variables $x_{v, n}$ which are 1 if vertex $v$ is colored with $n$ 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)$$\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)$$\min \quad \sum_{n=0}^{N-1} \sum_{(uv) \in E} x_{u, n} x_{v, n}$$

where $E$ is a set of edges on graph $G$.

$x_{u,n}$	$x_{v,n}$	$x_{u,n}x_{v,n}$
0	0	0
0	0	0
1	0	0
1	1	1

Since $x_{u,n}=1$ if vertex $u$ is colored by $n$ as defined above, $x_{u,n}x_{v,n}=1$ in the table above only when both $x_{u,n}$ and $x_{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)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 import jijmodeling as jm
      3 # define variables
      4 V = jm.Placeholder('V')

ModuleNotFoundError: No module named 'jijmodeling'

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 $u$ and $v$ 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 $\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

$$\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.

import networkx as nx

# 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}

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)