1. 3-JijModeling with OpenJij#

Open in Colab

In this chapter, first we explain how to write mathmatical model with JijModeling. After that, we explaint how to convert the model to QUBO by using JijModeling Transpiler and run Simulated Annealing with OpenJij. We solve “Creek Coverage Problem” as an example.

Please check document for more detail explanation about JijModeling and JijModeling Transpiler.

We can install jijmodeling with the following command using pip

!pip install jijmodeling
Requirement already satisfied: jijmodeling in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (0.10.0)
Requirement already satisfied: pydantic<1.10.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.9.2)
Requirement already satisfied: pandas<1.4.2 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.4.1)
Requirement already satisfied: python-ulid<1.2.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.1.0)
Requirement already satisfied: jij-cimod<1.5.0,>=1.4.1 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.4.36)
Requirement already satisfied: typeguard<2.14.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (2.13.3)
Requirement already satisfied: jijmodeling-schema==0.0.17 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (0.0.17)
Requirement already satisfied: dimod<0.12.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (0.10.17)
Requirement already satisfied: openjij<0.6.0,>=0.5.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (0.5.33)
Requirement already satisfied: numpy<1.24.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.23.2)
Requirement already satisfied: scipy<1.10.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling) (1.9.1)
Requirement already satisfied: betterproto[compiler]==1.2.5 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jijmodeling-schema==0.0.17->jijmodeling) (1.2.5)
Requirement already satisfied: stringcase in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (1.2.0)
Requirement already satisfied: grpclib in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (0.4.3)
Requirement already satisfied: black in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (22.6.0)
Requirement already satisfied: jinja2 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (3.1.2)
Requirement already satisfied: protobuf in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (4.21.5)
Requirement already satisfied: pyparsing<3.0.0,>=2.4.7 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from dimod<0.12.0->jijmodeling) (2.4.7)
Requirement already satisfied: requests<2.29.0,>=2.28.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from openjij<0.6.0,>=0.5.0->jijmodeling) (2.28.1)
Requirement already satisfied: pytz>=2020.1 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from pandas<1.4.2->jijmodeling) (2022.2.1)
Requirement already satisfied: python-dateutil>=2.8.1 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from pandas<1.4.2->jijmodeling) (2.8.2)
Requirement already satisfied: typing-extensions>=3.7.4.3 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from pydantic<1.10.0->jijmodeling) (4.3.0)
Requirement already satisfied: six>=1.5 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from python-dateutil>=2.8.1->pandas<1.4.2->jijmodeling) (1.16.0)
Requirement already satisfied: urllib3<1.27,>=1.21.1 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from requests<2.29.0,>=2.28.0->openjij<0.6.0,>=0.5.0->jijmodeling) (1.26.12)
Requirement already satisfied: idna<4,>=2.5 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from requests<2.29.0,>=2.28.0->openjij<0.6.0,>=0.5.0->jijmodeling) (3.3)
Requirement already satisfied: certifi>=2017.4.17 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from requests<2.29.0,>=2.28.0->openjij<0.6.0,>=0.5.0->jijmodeling) (2022.6.15)
Requirement already satisfied: charset-normalizer<3,>=2 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from requests<2.29.0,>=2.28.0->openjij<0.6.0,>=0.5.0->jijmodeling) (2.1.1)
Requirement already satisfied: click>=8.0.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from black->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (8.1.3)
Requirement already satisfied: mypy-extensions>=0.4.3 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from black->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (0.4.3)
Requirement already satisfied: pathspec>=0.9.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from black->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (0.9.0)
Requirement already satisfied: platformdirs>=2 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from black->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (2.5.2)
Requirement already satisfied: tomli>=1.1.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from black->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (2.0.1)
Requirement already satisfied: h2<5,>=3.1.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from grpclib->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (4.1.0)
Requirement already satisfied: multidict in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from grpclib->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (6.0.2)
Requirement already satisfied: hpack<5,>=4.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from h2<5,>=3.1.0->grpclib->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (4.0.0)
Requirement already satisfied: hyperframe<7,>=6.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from h2<5,>=3.1.0->grpclib->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (6.0.1)
Requirement already satisfied: MarkupSafe>=2.0 in /home/hiromichi/.pyenv/versions/3.9.6/lib/python3.9/site-packages (from jinja2->betterproto[compiler]==1.2.5->jijmodeling-schema==0.0.17->jijmodeling) (2.1.1)
WARNING: You are using pip version 21.1.3; however, version 22.2.2 is available.
You should consider upgrading via the '/home/hiromichi/.pyenv/versions/3.9.6/bin/python3.9 -m pip install --upgrade pip' command.

1.1. Formulation of QUBO with JijModeling#

JijModeling is a intuitive modeling library for fomulating mathmatical model and we can convert mathmatical model to QUBO easily. In the previous chapters, we have shown the case without JijModeling, so we had to formulate QUBO, then expand the expressions ourselves and put them into the Python script. However, we can eliminate that hassles with JijModeling.

JijModeling is a handy library that can help us reduce the computational and implementation errors in our QUBO and Ising model transformations.

Let us solve the Creek Coverage Problem as as example.

For more details of this problem, see also here (T-Wave: creek coverage problem (only Japanese)).

We introduce the formulation of the creek coverage problem as a mathmatical model.

This problem is whethre the graph G=(V,E)G=(V, E) can be covered by nn creeks.

The mathmatical model of this problem is

H=i=1n[12(1+vVxv,i)vVxv,i(u,v)Exu,ixv,i]H = \sum^n_{i=1}\left[ \frac{1}{2}\left(-1+\sum_{v \in V} x_{v,i}\right)\sum_{v \in V} x_{v, i} - \sum_{(u, v)\in E} x_{u,i} x_{v, i}\right]
s.t. i=1nxv,i=1forall v\mathrm{s.t.\ }\quad \sum^n_{i=1} x_{v, i} = 1\quad \mathrm{forall}\ v

Here, xv,ix_{v,i} is binary variable and if vertex vv is colored by iith color, then xv,i=1x_{v,i} = 1. The first term is Objective function which shows how close the split subgraph is to creek (complete graph) Constraint is that only one color is painted on each vertex. Both term must be zero. However, we treat the first term as a penalty term, and second as a cost(objective function).

The QUBO of this model as follows.

H=Av(1i=1nxv,i)2+Bi=1n[12(1+vVxv,i)vVxv,i(u,v)Exu,ixv,i]H = A\sum_v \left(1-\sum^n_{i=1} x_{v, i}\right)^2 + B \sum^n_{i=1}\left[ \frac{1}{2}\left(-1+\sum_{v \in V} x_{v,i}\right)\sum_{v \in V} x_{v, i} - \sum_{(u, v)\in E} x_{u,i} x_{v, i}\right]

Normally, we have write down QUBO model to use Ising optimization, however, we do not need to do so if you use JijModeling.

We give the Graph and the number of creek nn as follows in this time.

# set the number of vertex
N_VER = 8
# set the number of colors
N_COLOR = 3
# set the graph. define them which vertices are connected to each other
edges = [[0,1], [0,2], [1,2], [5,6], [2,3], [2,5], [3,4], [5,7], [7, 6]]

1.1.1. Formulation with JijModeling#

We import JijModeling.

import jijmodeling as jm

At First, we prepare variables for representing mathmatical model. We set an array of variables using Array. In this time, we need the number of (N_VER) x (N_COLOR), therefore we set shape argument as follows.

problem = jm.Problem('creek')

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

objective = jm.Sum(i, 1/2 * ( -1 + jm.Sum(v,x[v,i]) ) * jm.Sum(v,x[v,i]) - jm.Sum(e,x[e[0],i] * x[e[1],i]))
problem += objective
constraint = jm.Constraint("onehot",jm.Sum(i,x[v,i]) == 1,forall= v)
problem += constraint
problem
Problem: creekmini=0N1(0.5(v=0V1xv,i1)v=0V1xv,ieExe0,ixe1,i)s.t.onehot:i=0N1xv,i=1, v{0,,V1}xi0,i1{0,1}\begin{alignat*}{4}\text{Problem} & \text{: creek} \\\min & \quad \sum_{ i = 0 }^{ N - 1 } \left( 0.5 \cdot \left( \sum_{ v = 0 }^{ V - 1 } x_{v,i} - 1 \right) \cdot \sum_{ v = 0 }^{ V - 1 } x_{v,i} - \sum_{ e \in E } x_{e_{0},i} \cdot x_{e_{1},i} \right) \\\text{s.t.} & \\& \text{onehot} :\\ &\quad \quad \sum_{ i = 0 }^{ N - 1 } x_{v,i} = 1,\ \forall v \in \left\{ 0 ,\ldots , V - 1 \right\} \\[8pt]& x_{i_{0},i_{1}} \in \{0, 1\}\end{alignat*}

We can write the mathmatical model simple way.

Next, we need to prepare the instance data for Placeholder value.

instance_data = {'N':N_COLOR,'V':N_VER,'E':edges }

We finish to prepare the mathmatical model and instance data.

1.1.2. Converting mathmatical model to QUBO#

first we need to import transpiler function to create QUBO from mathmatical model.

from jijmodeling.transpiler.pyqubo.to_pyqubo import to_pyqubo
pyq_obj, pyq_cache = to_pyqubo(problem, instance_data,fixed_variables={})

to_pyqubo() creates pyqubo object (pyq_obj) and the information of the relationship between pyqubo object and mathmatical model is in pyq_cache. Plaese see the Documentation of JijModelingTranspiler for more detail information about to_pyqubo().

We can easily converted to QUBO (Python dictionary type) with pyq_obj.compile().to_qubo().

In OpenJij and D-Wave Ocean, QUBO is assumed to be represented by a Python dictionary type.

We can run it on each solver by .compile.

# compile this model
qubo, offset = pyq_obj.compile().to_qubo(feed_dict = {'onehot':1.0})

qubo is set to QUBO and offset is set to the constant that appears when it is converted to QUBO.

1.2. Run with OpenJij#

Let’s use OpenJij to solve creek coverage problem.

In this tutorial, we only use Simulated Annealing(SA) solver, however we can also run Simulated Quantum Annealing(SQA) as same way as SA.

# use SA on neal
import openjij as oj
sampler = oj.SASampler()
response = sampler.sample_qubo(qubo)

.first.sample extracts the lowest energy of all derived solutions.

print(response.first.sample)
{'x[]0_0': 0, 'x[]0_1': 0, 'x[]0_2': 1, 'x[]1_0': 0, 'x[]1_1': 0, 'x[]1_2': 1, 'x[]2_0': 0, 'x[]2_1': 0, 'x[]2_2': 1, 'x[]3_0': 1, 'x[]3_1': 0, 'x[]3_2': 0, 'x[]4_0': 1, 'x[]4_1': 0, 'x[]4_2': 0, 'x[]5_0': 0, 'x[]5_1': 1, 'x[]5_2': 0, 'x[]6_0': 0, 'x[]6_1': 1, 'x[]6_2': 0, 'x[]7_0': 0, 'x[]7_1': 1, 'x[]7_2': 0}

We can use .decode method to see the result more pretty.

result = pyq_cache.decode(response)
result.record.solution
{'x': [(([3, 4, 5, 6, 7, 0, 1, 2], [0, 0, 1, 1, 1, 2, 2, 2]),
   [1, 1, 1, 1, 1, 1, 1, 1],
   ())]}

The solution is in the COO format. It means that the solution array containts only indexed with a value of 1. This format is convinient to see the result becuase normally we only know which value is 1 or not. Let us see the result.

import networkx as nx
import matplotlib.pyplot as plt
# initialize vertex color list
node_colors = [-1] * N_VER
# set color list for visualization
colorlist = ['gold', 'violet', 'limegreen', 'darkorange']
# set vertex color list
for node_num,class_num in zip(*result.record.solution['x'][0][0]):
    node_colors[node_num] = colorlist[class_num]
# make figure
fig = plt.figure()
G = nx.Graph()
G.add_nodes_from(range(N_VER))
G.add_edges_from(instance_data["E"])
nx.draw_networkx(G, node_color=node_colors, with_labels=True)
../../_images/003-JijModeling_with_OpenJij_31_0.png

The graph is divided by each creeks.

We can check the energy and objective value by using result.evaluation

result.evaluation
Evaluation(energy=[-8.0], objective=[0.0], constraint_violations={'onehot': [0.0]}, penalty=[{}])

1.3. Conclusion#

We learned how to formulate it using JijModeling and how it works with OpenJij.

Procedures are as follows.

  1. Write down the mathmatical model by using JijModeling

  2. Convert mathmatical model to QUBO by using JijModeling Transpiler

  3. compile QUBO and convert it to a dictionary type

  4. solve optimization problems using OpenJij’s solver such as SASampler()

  5. decode solution by using decode.

JijModeling is useful and powerful tool for formulationg and JijModeling Transpiler provides easy interface to convert mathmatical model to QUBO. When we use in conjunction with OpenJij, which provides a variety of solvers, it provides comfortable development experience.