Mathematical Model Formulation using JijModeling and Optimization with OpenJij

Mathematical Model Formulation using JijModeling and Optimization with OpenJij#

In this tutorial, we explain the process of formulating a mathematical model using JijModeling, converting the mathematical model to QUBO, and solving it with OpenJij.

First, install the required packages. Install JijModeling, a module to easily build mathematical models, and jijmodeling-transpiler, a module for converting mathematical models using JijModeling to QUBO. These can be installed using pip.

# !pip install jijmodeling
# !pip install jijmodeling-transpiler

import jijmodeling as jm
import numpy as np
import matplotlib.pyplot as plt

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 import jijmodeling as jm
      2 import numpy as np
      3 import matplotlib.pyplot as plt

ModuleNotFoundError: No module named 'jijmodeling'

Traveling Salesman Problem (TSP)#

We discuss the traveling salesman problem (TSP) as an example of a constrained optimization problem. Suppose a salesman travels once to each of the cities to sell a product and then returns to the city he started from. The problem is to find the route with the shortest distance to reduce the cost of travel.

Constraints#

In this problem, there are two constraints: a location constraint, which states that a salesman can only visit each point once, and a time constraint, which states that since there is only one salesman, he can only be in one city at a given time.

Using a binary variable with $x_{t,i}=1$ when visiting the $i$ th city at time $t$ and $x_{t,i}=0$ otherwise, the above two constraints are:

\text{Location constraint : }\sum_{t=1}^N x_{t,i}=1 \quad \forall i

\text{Time constraint : }\sum_{i=1}^N x_{t,i}=1 \quad \forall t

A one-hot constraint is a type of constraint in which one of the above variables is 1.

Objective Function#

TSP is a problem of finding the shortest route. Therefore, if $d_{ij}$ is the distance between cities $i$ and $j$ , the distance traveled when visiting city $i$ at time $t$ and city $j$ at time $t+1$ is:

d_{ij}x_{t,i}x_{t+1,j}

The sum of the above is:

\sum_{t=1}^N\sum_{i=1}^N \sum_{j=1}^N d_{ij}x_{t,i}x_{t+1,j}

This is the total distance traveled, which is the objective function we wish to minimize.

To perform Ising optimization as described in the previous tutorials, a mathematical model with such constraints must be converted to an Ising Hamiltonian or QUBO Hamiltonian. Doing such work by hand is tedious and may cause bugs between the actual mathematical model and QUBO. JijModeling can do all this work automatically. In other words, it can code the mathematical model constructed as described above and automatically convert it to QUBO. In this section, we explain how to use JijModeling to solve TSP.

Building a Mathematical Model of the TSP using JijModeling#

First, we use JijModeling to describe the mathematical model of the problem. Unlike common modelers for mathematical optimization calculations, JijModeling builds the mathematical model independently from the data of the problem instance. By constructing the mathematical model this way, the generality of the mathematical model can be ensured. Moreover, mathematical equations can be described intuitively, just like writing mathematical equations on paper. Furthermore, the mathematical model described in JijModeling can be checked in LaTeX on the notebook.

In this section, we construct mathematical models one by one with JijModeling.

First, let us define the variables and the constants of the problem.

dist = jm.Placeholder("dist", dim=2)
N = jm.Placeholder("N")
x = jm.Binary("x", shape=(N, N))
i = jm.Element("i", (0,N))
j = jm.Element("j", (0,N))
t = jm.Element("t", (0,N))

Here, jm.Placeholder represents a constant, which is the distance matrix and the number of cities. By varying the distance matrix and number of cities data, we represent various sizes of TSP.

Binary variables are represented by jm.Binary. Here we define a binary variable of $N\times N$ . Then, we use jm.Element to define the subscripts i,j,t. These are used to represent the range of sums.

In JijModeling, we create a jm.Problem instance and add objective functions and constraints to it. Next, we will define the objective function using the variables we have defined.

problem = jm.Problem("TSP")
obj = jm.Sum([t, i, j], dist[i, j] * x[t, i] * x[(t + 1) % N, j])
problem += obj
problem

\begin{alignat*}{4}\text{Problem} & \text{: TSP} \\\min & \quad \sum_{ t = 0 }^{ N - 1 } \sum_{ i = 0 }^{ N - 1 } \sum_{ j = 0 }^{ N - 1 } dist_{i,j} \cdot x_{t,i} \cdot x_{\left( t + 1 \right) \mod N,j} \\& x_{i_{0},i_{1}} \in \{0, 1\}\end{alignat*}

The sum can be expressed with jm.Sum. The first argument of jm.Sum is the indices to be summed, and since the objective function of TSP takes sums for three indices, we pass those indices (jm.element) in a list.

Then, we add the constraint conditions.

# Constraint 1 : one-hot position constraint
problem += jm.Constraint(
            "one-hot location",
            jm.Sum(t,x[t,i]) == 1,
            forall=i,
        )

# Constraint 2 : one-hot time constraint
problem += jm.Constraint(
            "one-hot time",
            x[t, :] == 1,
            forall=t,
        )

Constraints can be expressed using jm.Constraint. The first argument is the name of the constraint condition, and the second argument is a mathematical expression of the constraint condition.

This constraint has an optional argument, forall. This is a JijModeling argument that expresses what is expressed in a mathematical model as “for any $i$ ” or “ $\forall i$ ”.

Finally, let us check the mathematical model we have just described.

problem

\begin{alignat*}{4}\text{Problem} & \text{: TSP} \\\min & \quad \sum_{ t = 0 }^{ N - 1 } \sum_{ i = 0 }^{ N - 1 } \sum_{ j = 0 }^{ N - 1 } dist_{i,j} \cdot x_{t,i} \cdot x_{\left( t + 1 \right) \mod N,j} \\\text{s.t.} & \\& \text{one-hot location} :\\ &\quad \quad \sum_{ t = 0 }^{ N - 1 } x_{t,i} = 1,\ \forall i \in \left\{ 0 ,\ldots , N - 1 \right\} \\[8pt]& \text{one-hot time} :\\ &\quad \quad \sum_{ \bar{i}_{1} = 0 }^{ N - 1 } x_{t,\bar{i}_{1}} = 1,\ \forall t \in \left\{ 0 ,\ldots , N - 1 \right\} \\[8pt]& x_{i_{0},i_{1}} \in \{0, 1\}\end{alignat*}

We see the same mathematical expression displayed as in the mathematical model used in the explanation.

This completes the construction of the mathematical model. As above, JijModeling allows you to code mathematical models by comparing them with mathematical formulas.

Creating the Problem Data#

Now that we have a mathematical model of the problem, the next step is to create data for the problem. Here we will solve a simple problem with 5 cities and random distances between cities.

N = 5
np.random.seed(3)

x_pos = np.random.rand(N) 
y_pos = np.random.rand(N) 

plt.plot(x_pos, y_pos, 'o')
plt.xlim(0, 1)
plt.ylim(0, 1)

(0.0, 1.0)

../../_images/94d60c118d6cd268569b4df682b48432b89970479a717b80d8381b2c0011a109.png

Since we assign the data to the jm.Placeholder to create the mathematical model, we need to pass the data in a dictionary type with the Placeholder’s name as the key. In this problem, we need to pass values for N and dist.

XX, XX_T = np.meshgrid(x_pos, x_pos)
YY, YY_T = np.meshgrid(y_pos, y_pos)
distance = np.sqrt((XX - XX_T)**2 + (YY - YY_T)**2)
instance_data = {
    "N":N,"dist": distance
}
instance_data

{'N': 5,
 'dist': array([[0.        , 0.7866063 , 0.73643374, 0.84577089, 0.56967619],
        [0.7866063 , 0.        , 0.4251585 , 0.21078131, 0.36540009],
        [0.73643374, 0.4251585 , 0.        , 0.26950348, 0.64576184],
        [0.84577089, 0.21078131, 0.26950348, 0.        , 0.54552992],
        [0.56967619, 0.36540009, 0.64576184, 0.54552992, 0.        ]])}

Convert Mathematical Models to QUBO using JijModeling-Transpiler#

Now that the mathematical model and data are ready, we convert the mathematical model and data to QUBO using JijModeling-Transpiler.

First, import to_pyqubo, a function to convert to QUBO.

from jijmodeling.transpiler.pyqubo import to_pyqubo

We create a pyqubo object by giving this to_pyqubo a mathematical model and the data of the problem. Note that, if we want to fix some of the variables to a certain value, we can give them as the third variable in a dictionary type.

model,cache = to_pyqubo(problem,instance_data,{})

To generate QUBO, we pass the magnitude of the coefficients of the constraints to the pyqubo object and then use the to_qubo method.

multipliers = {"one-hot location":1.0,"one-hot time":1.0}
Q,offset = model.compile().to_qubo(feed_dict = multipliers)

We have successfully generated QUBO.

Performing Optimization using OpenJij#

Since QUBO has been obtained, optimization calculations can be performed as before using this QUBO.

import openjij as oj

sampler = oj.SASampler(num_reads=100)
res = sampler.sample_qubo(Q=Q)

The JijModeling-Transpiler function will format the results obtained by optimization into a more readable form which is the SampleSet class. Let us use the decode function.

result = cache.decode(res)
result

SampleSet(record=Record(solution={'x': [(([1, 0, 2, 3, 4], [3, 2, 1, 4, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 2, 3, 1, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 2, 3, 1, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 1, 4, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 4, 1]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 2, 3, 1, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 1, 3]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 2, 3, 1, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 2, 3, 1, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 1, 4, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 4, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 4, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 4, 1]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 4, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 1, 0, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 2, 3, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 1, 2, 0, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 1, 0, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 1, 0, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 1, 2, 0, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 2, 3, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 2, 3, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 3, 2, 1]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 3, 2, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 4, 2, 3, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 1, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 1, 4, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 3, 4, 1, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 1, 4, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 0, 4, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 1, 0, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 1, 0, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 0, 4, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 0, 4, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 3, 0, 4, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 1, 0, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 1, 3, 2, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 1, 3, 2]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [1, 0, 4, 2, 3]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [1, 0, 4, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 4, 3, 1, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 1, 2, 4, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [1, 0, 4, 2, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 4, 0, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 1, 4, 0, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 3, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 2, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 2, 3, 4, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 3, 1, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 4, 2, 1, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 1, 0, 4, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 3, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 4, 3, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 1, 3, 4, 0]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 3, 2, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 1, 0, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 4, 3, 2, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 1, 0, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 1, 2, 3, 4]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 1, 2, 3, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 3, 0, 1, 2]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [1, 0, 4, 3, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 1, 0, 4, 2]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [1, 2, 3, 0, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 1, 3, 2, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 2, 1, 4, 3]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [3, 2, 4, 1, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [2, 3, 0, 1, 4]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 2, 1, 3, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [0, 3, 2, 4, 1]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 2, 1, 3, 0]), [1, 1, 1, 1, 1], ()), (([1, 0, 2, 3, 4], [4, 2, 1, 0, 3]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 1, 4, 2, 3]), [1, 1, 1, 1, 1], ()), (([0, 1, 2, 3, 4], [0, 1, 3, 4, 2]), [1, 1, 1, 1, 1], ())]}, num_occurrences=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), evaluation=Evaluation(energy=[-7.848205186671935, -7.512420345981557, -7.512420345981557, -7.517670867792821, -7.5176708677928215, -7.195852125954437, -7.848205186671935, -7.848205186671935, -7.403525608627656, -7.517670867792821, -7.848205186671935, -7.517670867792821, -7.512420345981557, -7.848205186671935, -7.403525608627656, -7.848205186671935, -7.848205186671935, -7.5176708677928215, -7.848205186671935, -7.403525608627657, -7.403525608627657, -7.848205186671935, -7.403525608627657, -7.848205186671934, -7.848205186671934, -7.517670867792821, -7.848205186671935, -7.5176708677928215, -7.848205186671935, -7.5176708677928215, -7.848205186671935, -7.512420345981557, -7.524490846313727, -7.403525608627657, -7.848205186671934, -7.848205186671935, -7.403525608627657, -7.29652646979358, -7.524490846313728, -7.848205186671935, -7.403525608627657, -7.848205186671935, -7.848205186671935, -7.848205186671935, -7.296526469793579, -7.195852125954437, -7.195852125954437, -7.5176708677928215, -7.512420345981557, -7.848205186671934, -7.524490846313728, -7.848205186671935, -7.848205186671935, -7.524490846313727, -7.524490846313727, -7.848205186671935, -7.848205186671935, -7.517670867792821, -7.848205186671935, -7.848205186671935, -7.074886888268367, -7.848205186671935, -7.296526469793579, -7.5176708677928215, -7.848205186671935, -7.302851264788513, -7.512420345981557, -7.512420345981557, -7.524490846313728, -7.296526469793579, -7.302851264788514, -7.848205186671935, -7.524490846313728, -7.5176708677928215, -7.524490846313728, -7.086957388600537, -7.512420345981557, -7.848205186671935, -7.848205186671935, -7.086957388600536, -7.517670867792821, -7.524490846313728, -7.848205186671935, -7.5176708677928215, -7.848205186671935, -7.848205186671935, -7.848205186671934, -7.524490846313728, -7.848205186671935, -7.512420345981558, -7.848205186671935, -7.848205186671935, -7.848205186671934, -7.848205186671934, -7.517670867792821, -7.403525608627657, -7.848205186671935, -7.848205186671935, -7.848205186671935, -7.848205186671935], objective=[2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.151794813328065, 2.1517948133280655, 2.151794813328065, 2.151794813328065, 2.1517948133280655, 2.151794813328065, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4755091536862723, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.48232913220718, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.4823291322071794, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.487579654018443, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.596474391372343, 2.6971487352114867, 2.6971487352114862, 2.703473530206421, 2.703473530206421, 2.703473530206421, 2.703473530206421, 2.8041478740455634, 2.8041478740455634, 2.8041478740455634, 2.913042611399464, 2.913042611399464, 2.9251131117316342], constraint_violations={'one-hot location': [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], 'one-hot time': [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]}, penalty={}), measuring_time=MeasuringTime(solve=SolvingTime(preprocess=None, solve=None, postprocess=None), system=SystemTime(post_problem_and_instance_data=None, request_queue=None, fetch_problem_and_instance_data=None, fetch_result=None, deserialize_solution=None), total=None))

SampleSet.Record mainly stores the solutions and the occurrences of the solutions. The obtained solution is contained in the solution which is in the result.record as a sparse matrix. The first two elements are critical: the first is the index in the matrix, and the second is the value of that index. In the case of a binary variable, only the value that is 1 is stored, so the value usually contains only 1. SampleSet.lowest() method extracts the solutions taking the minimum value of the objective functions among the feasible solutions. If there are multiple minimum values, lowest() method returns all these solutions.

sparse_index,value,_ = result.lowest().record.solution['x'][0]
sparse_index

([1, 0, 2, 3, 4], [3, 2, 1, 4, 0])

In result.evaluation, there is energy, objective function, and constraint violation. These represent the evaluation values obtained by optimization. Here, we check whether the solution satisfies the constraints.

result.evaluation.constraint_violations

{'one-hot location': [0.0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0],
 'one-hot time': [0.0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]}

This shows that we have obtained a solution that satisfies the constraints.

Let us visualize this solution. When plotting the route, we can get the order in which to move around the cities by sorting the city indices using the time-related indices.

time_indices, city_indices = zip(*sorted(zip(*sparse_index)))
time_indices, city_indices

((0, 1, 2, 3, 4), (2, 3, 1, 4, 0))

plt.plot(x_pos, y_pos, 'o',markersize=12)
plt.xlim(0, 1)
plt.ylim(0, 1)

for i, city_index in enumerate(city_indices[:-1]):
    next_city_index = city_indices[i+1]
    plt.plot([x_pos[city_index],x_pos[next_city_index ]],[y_pos[city_index],y_pos[next_city_index ]],c = "blue")
    
plt.plot([x_pos[city_indices[-1]],x_pos[city_indices[0]]],[y_pos[city_indices[-1]],y_pos[city_indices[0]]],c = "blue")

[<matplotlib.lines.Line2D at 0x11ffc2d00>]

../../_images/a46a11b9740ec752ce02b3289a07c346af57aacd31b236cd1959bf7678b3556e.png