How to decode the original solution

In this tutorial, we will show you how to decode the original solution to JijModeling's schema using JijModeling-Transpiler.

import jijmodeling as jm
import jijmodeling_transpiler as jmt

import jijmodeling as jm
import openjij as oj
import jijmodeling_transpiler as jmt
import numpy as np
import matplotlib.pyplot as plt

d = jm.Placeholder("d", ndim=2)
n = d.len_at(0, latex="n")

i, j, t = jm.Element("i", n), jm.Element("j", n), jm.Element("t", n)

x = jm.BinaryVar("x", shape=(n, n))

problem = jm.Problem("TSP")
# Objective function
problem += jm.sum([i, j], d[i, j]*jm.sum(t, x[i, t]*x[j, (t+1) % n]))

# Constraints
jmC = jm.Constraint
problem += jmC("one-time", x[i, :].sum() == 1, forall=i)
problem += jmC("one-city", x[:, t].sum() == 1, forall=t)

problem

$\begin{array}{cccc}\text{Problem:} & \text{TSP} & & \\& & \min \quad \displaystyle \sum_{i = 0}^{n - 1} \sum_{j = 0}^{n - 1} d_{i, j} \cdot \sum_{t = 0}^{n - 1} x_{i, t} \cdot x_{j, \left(t + 1\right) \bmod n} & \\\text{{s.t.}} & & & \\ & \text{one-city} & \displaystyle \sum_{\ast_{0} = 0}^{n - 1} x_{\ast_{0}, t} = 1 & \forall t \in \left\{0,\ldots,n - 1\right\} \\ & \text{one-time} & \displaystyle \sum_{\ast_{1} = 0}^{n - 1} x_{i, \ast_{1}} = 1 & \forall i \in \left\{0,\ldots,n - 1\right\} \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}$

# Prepare data to create instance
def random_2d_tsp(n: int):
    x = np.random.uniform(0, 1, n)
    y = np.random.uniform(0, 1, n)
    XX, YY = np.meshgrid(x, y)
    distance = np.sqrt((XX - XX.T)**2 + (YY - YY.T)**2)
    return distance, (x, y)

num_city = 10
distance, (pos_x, pos_y) = random_2d_tsp(n=num_city)

plt.scatter(pos_x, pos_y)
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.show()

# Substitute data to the mathematical model
compiled_instnace = jmt.core.compile_model(problem, {"d": distance})

# Transpile to QUBO
qubo_builder = jmt.core.pubo.transpile_to_pubo(compiled_instnace)

In jijmodeling-transpiler, after assigning values to placeholders (after .compile_model), all decision variables are labeled with integer labels, and then expressions are expressed using those integer labels.

# description label         subscripts   value
var_map: dict[str, dict[tuple[int, ...], float]] = compiled_instnace.var_map.var_map

print(var_map)

{'x': {(0, 0): 0, (0, 1): 1, (0, 2): 2, (0, 3): 3, (0, 4): 4, (0, 5): 5, (0, 6): 6, (0, 7): 7, (0, 8): 8, (0, 9): 9, (1, 1): 10, (1, 2): 11, (1, 3): 12, (1, 4): 13, (1, 5): 14, (1, 6): 15, (1, 7): 16, (1, 8): 17, (1, 9): 18, (1, 0): 19, (2, 1): 20, (2, 2): 21, (2, 3): 22, (2, 4): 23, (2, 5): 24, (2, 6): 25, (2, 7): 26, (2, 8): 27, (2, 9): 28, (2, 0): 29, (3, 1): 30, (3, 2): 31, (3, 3): 32, (3, 4): 33, (3, 5): 34, (3, 6): 35, (3, 7): 36, (3, 8): 37, (3, 9): 38, (3, 0): 39, (4, 1): 40, (4, 2): 41, (4, 3): 42, (4, 4): 43, (4, 5): 44, (4, 6): 45, (4, 7): 46, (4, 8): 47, (4, 9): 48, (4, 0): 49, (5, 1): 50, (5, 2): 51, (5, 3): 52, (5, 4): 53, (5, 5): 54, (5, 6): 55, (5, 7): 56, (5, 8): 57, (5, 9): 58, (5, 0): 59, (6, 1): 60, (6, 2): 61, (6, 3): 62, (6, 4): 63, (6, 5): 64, (6, 6): 65, (6, 7): 66, (6, 8): 67, (6, 9): 68, (6, 0): 69, (7, 1): 70, (7, 2): 71, (7, 3): 72, (7, 4): 73, (7, 5): 74, (7, 6): 75, (7, 7): 76, (7, 8): 77, (7, 9): 78, (7, 0): 79, (8, 1): 80, (8, 2): 81, (8, 3): 82, (8, 4): 83, (8, 5): 84, (8, 6): 85, (8, 7): 86, (8, 8): 87, (8, 9): 88, (8, 0): 89, (9, 1): 90, (9, 2): 91, (9, 3): 92, (9, 4): 93, (9, 5): 94, (9, 6): 95, (9, 7): 96, (9, 8): 97, (9, 9): 98, (9, 0): 99}}

Evaluate from a matrix value

tour = np.arange(num_city, dtype=int)
np.random.shuffle(tour) 
tour = np.append(tour, tour[0]) # Add the first city to the end for the tour
x_matrix = np.zeros((num_city, num_city))
for t, i in enumerate(tour[:-1]):
    x_matrix[i, t] = 1
print(x_matrix)

[[0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
 [0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]
 [0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]]

# Convert to dict[int, float] from x_matrix
x_dict_value = {}
for i in range(num_city):
    for t in range(num_city):
        x_dict_value[var_map["x"][(i, t)]] = x_matrix[i, t]

eval_result = jmt.core.decode.evaluate([x_dict_value], compiled_instnace)
eval_result

Evaluation(energy=[], objective=[6.734676566222796], constraint_violations={"one-city": [0.0], "one-time": [0.0]}, constraint_forall={}, constraint_values=[], penalty={})

Decode from dimod.SampleSet

# D-Wave's Simulated Annelaing Sampler 
!pip install dwave-neal

import neal
sa_sampler = neal.SimulatedAnnealingSampler()
qubo, _ = qubo_builder.get_qubo_dict()
response = sa_sampler.sample_qubo(qubo)

# `decode_from_openjij` method is also used for dimod.SampleSet
sample_set = jmt.core.pubo.decode_from_openjij(response, qubo_builder, compiled_instnace)
sample_set.evaluation

Evaluation(energy=[], objective=[4.510168426533271], constraint_violations={"one-city": [0.0], "one-time": [0.0]}, constraint_forall={}, constraint_values=[], penalty={})