Skip to main content

Samplers

JijZept has many kinds of solvers for mathematical models of optimization problems. We here show the detailed usage of these solvers. First, we explain common features of these solvers, then we describe how to read calculation status, error messages, and so on. Finally, we briefly demonstrate some solvers with specific features.

Basic Usage

In this section, we explain basic and common usage of JijZept, which has following samplers to solver optimization problems.

Set Up Samplers

The above sampler classes are provided in JijZept as a python module. One needs API key of JijZept to initialize these samplers. For example, the following code sets up jz.JijSASampler.

import jijzept as jz
sampler = jz.JijSASampler(token='*** your API key ***', url='https://api.jijzept.com')

One can also use config.toml file for the initialization.

import jijzept as jz
sampler = jz.JijSASampler(config='*** your config.toml path ***')

Here, the contents of config.toml file should be like as follows.

[default]
url = "https://api.jijzept.com/"
token = "*** your API key ***"

Third Party Solvers

Three solvers, JijDA3Sampler, JijLeapHybridCQMSampler, and JijFixstarsAmplifySampler need extra authentication information. One must need to contract and receive API key or something about each solver. For example, JijDA3Sampler can be initialized as follows.

import jijzept as jz
sampler = jz.JijDA3Sampler(
token='*** your API key ***',
url='https://api.jijzept.com',
da3_token='*** your DA3 token ***'
)

Or, one can also use

import jijzept as jz
sampler = jz.JijDA3Sampler(
config='*** your config.toml path ***',
da3_token='*** your DA3 token ***'
)

These solvers are named third party solvers.

Sampling Methods

Now, the above noted samplers have following methods.

  • sample_qubo: Solver for quadratic unconstrained binary optimization (QUBO) problems.
  • sample_hubo: Solver for higher-order unconstrained binary optimization (HUBO) problems.
  • sample_model: Solver for any mathematical models with using JijModeling.

Note here that sample_model is implemented in all the above samplers, but the others are not implemented in all samplers. In the following subsection, we explain how to use each methods.

QUBO sampler

QUBO problems like

mini<jQi,jqiqj,    with  qi{0,1}{\rm min}\sum_{i < j} Q_{i,j} q_i q_j,\;\;{\rm with}\;q_i\in\{0,1\}

can be solved by sample_qubo. For example,

mini=1Nj=i+1Nqiqj,    with  qi{0,1},  N=10{\rm min}\sum^{N}_{i=1}\sum^{N}_{j=i+1} q_i q_j,\;\;{\rm with}\;q_i\in\{0,1\},\;N=10

can be solved using sample_qubo in JijSASampler by this code.

import jijzept as jz

# Set up jz.JijSASampler
sampler = jz.JijSASampler(config='*** your config.toml path ***')

# Set the dimension of QUBO matirx.
N = 10

# Prepare QUBO matirx
Q = {}
for i in range(N):
for j in range(i+1, N):
Q[i,j] = 1.0

# Sample with sample_qubo
response = sampler.sample_qubo(Q)

# Print the solution with lowest energy.
print(response.first.sample)

# Print the lowest energy
print(response.first.energy)

Please check if the following solution is obtained. {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0} 0.0 This is the optimal solution. Here, the return value of sample_qubo is provided as dimod.SampleSet. Please see the official reference.

HUBO Sampler

HUBO problems like

mini<j<kQi,j,kqiqjqk,    with  qi{0,1}{\rm min}\sum_{i < j < k\ldots} Q_{i,j,k\ldots} q_i q_jq_k\ldots,\;\;{\rm with}\;q_i\in\{0,1\}

can be solved by sample_hubo. For example,

min  2q0q1q2q3q1q2q2q3,    with  qi{0,1}.{\rm min}\;2q_0q_1q_2q_3 - q_1q_2 - q_2q_3,\;\;{\rm with}\;q_i\in\{0,1\}.

can be solved using sample_hubo in JijSASampler by this code.

import jijzept as jz

# Set up jz.JijSASampler
sampler = jz.JijSASampler(config='*** your config.toml path ***')

# Prepare HUBO interaction
H = {(0,1,2,3): +2, (1,2): -1, (2,3): -1}

# Sample with sample_hubo
response = sampler.sample_hubo(H, vartype='BINARY')

# Print the solution with lowest energy.
print(response.first.sample)

# Print the lowest energy
print(response.first.energy)

Please check if the following solution is obtained. {0: 0, 1: 1, 2: 1, 3: 1} -2.0 This is the optimal solution.

Sample with JijModeling

One can construct mathematical models with using JijModeling. Please see the documentation for the detailed usage. Here, we use the simple example.

import jijmodeling as jm

d = jm.Placeholder('d', dim=1) # Define cariable d
d.shape[0].set_latex('N') # Set latex expression of the length of d
x = jm.Binary('x', shape=(d.shape[0],)) # Define binary variable
i = jm.Element('i', (0, d.shape[0])) # Define dummy index in summation
problem = jm.Problem('simple problem') # Create problem instance
problem += jm.Sum(i, d[i]*x[i]) # Add objective function
problem += jm.Constraint('one hot', jm.Sum(i, x[i]) == 1) # Add constraint condition
problem # Display the problem

Using the Jupyter Notebook environment, one can see the mathematical expression.

Then, we solve the problem by sample_model, which has the basic parameters.

ParametersDescription
feed_dictThe instance data to the placeholders.
multipliersThe multipliers for penalty terms, derived from constraint conditions. If the parameter search is enabled, this value used as initial values.
searchIf True, the parameter search will be enabled, which tries to find better values of multipliers for penalty terms from constraint conditions.
num_searchThe number of parameter search iteration. This option works when the parameter search is enabled.

sample_model has more tuning parameters depending on the samplers. See the class reference. Now, let us solve the problem by sample_model.

from jijzept import JijSASampler

# Instance data for d, the key is the name of placeholder and the value is actual values
instance_data = {'d': [1.0, 0.1, -2.0, 1.0]}

# Set up sampler
sampler = JijSASampler(config='*** your config.toml path ***')

# Solve by sample_model
response = sampler.sample_model(
problem,
instance_data,
multipliers={'one-hot': 1.0}, # The key is the name of constraint conditions.
search=True,
num_search=10
)

One can see the feasible solutions like this.

# Convert dense type to make it easy to see the solution
print(response.feasible().to_dense().record.solution)

# Display the objective value
print(response.feasible().evaluation.objective)

response has all the solutions at each parameter search step. Please check if the optimal and feasible solution (x0,x1,x2,x3)=(0,0,1,0)(x_0,x_1,x_2,x_3)=(0,0,1,0) with the objective value -2.0 are obtained. One can also check the constraint violations.

# Display how the constration conditions are violated
print(response.feasible().evaluation.constraint_violations)

Here the constraint violations represent how the constraints conditions are violated and are defined as

1+i=0N1xi,with  the  solution  xi\left\|-1+\sum^{N-1}_{i=0}x_i\right\|,{\rm with\;the\;solution}\;x_{i}

Available Options

The sampling methods, sample_qubosample_hubo, and sample_model provide two options, sync and time_out.

Sync Option

With the default settings, after throwing a problem to JijZept, the process blocks until the answer is returned, which can be inconvenient when solving process takes a long time. Setting the parameter to sync=False, which is the asynchronous mode, will return the control immediately after the problem is thrown to JijZept.

response = sampler.sample_model(
problem,
feed_dict={'d': data_d},
multipliers={'one-hot': 1.0},
search=True,
num_search=10,
sync=False, # Set to asynchronous mode
)

At this mode, one can obtain the result by get_result after the solving process is completed.

response.get_result()

Timeout Setting

The timeout option allows you to set a time limit on how long the solvers will run. If the computation time is exceeded, FAILED will be returned. The following example sets a time limit as 10 seconds.

response = sampler.sample_model(
problem,
feed_dict={'d': data_d},
multipliers={'one-hot': 1.0},
search=True,
num_search=10,
timeout=10 # seconds
)

Note that the default value of timeout is 3600 (one hour).

Solving Status and Error Messages

The return value of the samplers, the above mentioned response, stores calculation status of JijZept, which are the following types.

StatusDescription
SUCCESSCalculation was successfully completed.
PENDINGA problem has been submitted and has not yet been passed to solvers.
RUNNINGA problem has been submitted and passed to solvers.
FAILEDFailed to solver problems. See response.error_message for the details.
UNKNOWNERRORFailed to solver problems due to unexpected causes.

If the calculation status is FAILED, one can see the error messages in response.error_message. We here show the example by setting short calculation time, timeout=0.01.

response = sampler.sample_model(
problem,
feed_dict={'d': data_d},
multipliers={'one-hot': 1.0},
search=True,
num_search=10,
timeout=0.01 # seconds
)

print(response.status) # Show status
print(response.error_message) # Show error messages

We expect that the following output is showed.

Solvers with Specific Features

Some solvers in JijZept has specific features, satisfying some types of constraint conditions. In this section, we briefly explain these solvers.

JijSwapMovingSampler

When using an Ising solvers to solve problems with complex constraint conditions, situations often arise where it is difficult to find a solution that satisfies all the constraint conditions. JijSwapMovingSampler extracts the "n-hot" constraint conditions from the mathematical expressions by JijModeling and searches for a solution that satisfies those constraints. This makes it easier to find a solution that sees all constraints. Here, the "n-hot" constraint conditions mean the following type of constraint conditions.

ixi=n,    with    xi{0,1},    nZ\sum_{i}x_i=n,\;\;{\rm with}\;\;x_{i}\in\{0,1\},\;\;n\in \mathbb{Z}

Let us try the example in Sample with JijModeling section.

import jijmodeling as jm

d = jm.Placeholder('d', dim=1) # Define cariable d
d.shape[0].set_latex('N') # Set latex expression of the length of d
x = jm.Binary('x', shape=(d.shape[0],)) # Define binary variable
i = jm.Element('i', (0, d.shape[0])) # Define dummy index in summation
problem = jm.Problem('simple problem') # Create problem instance
problem += jm.Sum(i, d[i]*x[i]) # Add objective function
problem += jm.Constraint('one hot', jm.Sum(i, x[i]) == 1) # Add constraint condition
problem # Display the problem

This problem has the one-hot constraint conditions. JijSwapMovingSampler can find feasible solutions without the parameter search.

from jijzept import JijSwapMovingSampler

# Instance data for d
data_d = [1.0, 0.1, -2, 1]

# Set up sampler
sampler = JijSwapMovingSampler(config='*** your config.toml path ***')

# Solve by sample_model
response = sampler.sample_model(
problem,
feed_dict={'d': data_d}
)

# Convert dense type to make it easy to see the solution
print(response.to_dense().record.solution)

# Display the objective value
print(response.evaluation.objective)

# Display constraint violations
print(response.evaluation.constraint_violations)

Please check if the following outpu is obtained. {'x': [array([0, 0, 1, 0])]} [-2.0] {'one hot': [0.0]} This is the optimal solution.

info

When multiple n-hot constraint conditions exist, it works to ensure that at least one of the constraint conditions is always satisfied.

JijDA3Sampler

JijDA3Sampler can find the feasible solutions for one-way and two-way one-hot constraint conditions, where one-way one-hot constraint conditions mean just one-hot ones compared to two-way one-hot ones, and two-way one-hot ones are like the constraint conditions appeared in the traveling salesman problem (TSP).

i=0N1xi,t=1,    for  all  t=0,1,,N1t=0N1xi,t=1,    for  all  i=0,1,,N1\sum^{N-1}_{i=0}x_{i, t}=1,\;\;{\rm for\;all\;}t=0,1,\ldots,N-1\\ \sum^{N-1}_{t=0}x_{i, t}=1,\;\;{\rm for\;all\;}i=0,1,\ldots,N-1

Let us here use the TSP as an example of the problem with two-way one-hot constraint conditions.

import jijmodeling as jm

# Define variables
d = jm.Placeholder('d', dim=2)
N = d.shape[0].set_latex("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))

# Set problem
problem = jm.Problem('TSP')
problem += jm.Sum([i, j], d[i, j] * jm.Sum(t, x[i, t]*x[j, (t+1) % N]))
problem += jm.Constraint("one-city", x[:, t] == 1, forall=t)
problem += jm.Constraint("one-time", x[i, :] == 1, forall=i)

# Display mathematical expression
problem

Then, we solve the problem with two-dimensional random instance by JijDA3Sampler. There is no need to take some efforts to treat the constraint conditions. JijDA3Sampler extracts one-way and two-way one-hot constraint conditions and find feasible solutions.

import numpy as np
from jijzept import JijDA3Sampler

def tsp_distance(N: int):
x, y = np.random.uniform(0, 1, (2, N))
XX, YY = np.meshgrid(x, y)
distance = np.sqrt((XX - XX.T)**2 + (YY - YY.T)**2)
return distance, (x, y)


# Define the number of cities
num_cities = 10
distance, (x_pos, y_pos) = tsp_distance(N=num_cities)

# Setup SASampler
sampler = JijDA3Sampler(
config='*** your config.toml path ***',
da3_token='*** your DA3 token ***'
)
# Calculate by JijSASampler
response = sampler.sample_model(problem, {'d': distance})

# Display the objective value
print(response.evaluation.objective)

# Display constraint violations
print(response.evaluation.constraint_violations)

Please check the constraint violations are zero.