Solver

This section describes the solver class that solves the logical model by executing Ising machines.

Construct a Solver Object

A solver object is constructed using a client object as follows:

from amplify import BinaryPoly, gen_symbols, Solver
from amplify.client import FixstarsClient

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

solver = Solver(client)

You can also give a client object to the solver object later.

from amplify import Solver
from amplify.client import FixstarsClient

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

solver = Solver()
solver.client = client

Run the Solver and Obtain Solutions

You can run an Ising machine by providing an input model or a logical model to the solve() method.

The following logical model classes are the possible inputs for the solver class.

For simplicity, it is also possible to give a polynomial, matrix, or constraint object to solve() method. In this case, a logical model is automatically created accordingly to the type of given object. A combination of an objective function and constraint conditions, however, cannot be given to the solve() method this way. In such cases, a logical model object should be explicitly constructed, or use Addition Operator of the constraint object.

To use polynomials, the following arguments are given:

To use matrices, the following arguments are given. The second argument is the constant term.

solve(BinaryMatrix, float = 0.0)
solve(IsingMatrix, int = 0)
solve(BinaryIntMatrix float = 0.0)
solve(IsingIntMatrix, int = 0)

To use constraint objects, the following arguments are given:

Examples

Execution results will be returned as solve() method is executed. The following is an example of execution using the Amplify AE client.

from amplify import BinarySymbolGenerator, Solver
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout 1 second

solver = Solver(client)
result = solver.solve(f)

>>> f
2 q_0 q_1 q_2 - q_0 q_1 + q_2 + 1
>>> [f"energy = {s.energy}, q = {q.decode(s.values)}" for s in result]
['energy = 0.0, q = [1. 1. 0.]']

The result of executing the solve() method is an object with the following attributes:

solutions : A list of execution results. Each element has the following attributes.
- energy : The energy value (evaluated value of the input model).
- values : The values of the input variables as a list.
- frequency : The number of identical solutions.
- is_feasible : Whether the solution satisfies all constraints. By filtering solutions, only solutions with True are stored by default.

Using the following special method, the elements of solutions can be obtained by for loop or direct element access on the returned value.

__getitem__ : Return the element access solutions[n] of solutions transparently.
__len__ : Return the number of elements len(solutions) in solutions transparently.
__iter__ : Return the solutions iterator transparently.

Typically, the best solution of an execution result can be obtained from the first element (result[0]) in the following way:

>>> result[0].energy
0.0
>>> result[0].values
{2: 0, 1: 1, 0: 1}

However, when constraints are given, the solutions are filtered in such a way that only feasible solutions are contained in the result. If the length of result is 0, it indicates that no solution satisfying the constraints is found.

Filter Solutions

When a model that contains constraints are given to the solve() method, it will automatically filter out solutions of the input model that do not satisfy the constraints by default. The following is an example for imposing the constraint q[0] + q[1] == 1.

from amplify import BinarySymbolGenerator, Solver
from amplify.constraint import one_hot
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1
c = one_hot(q[0] + q[1])  # Constraint: q[0] + q[1] == 1

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

model = f + c
solver = Solver(client)
result = solver.solve(model)

>>> f
2 q_0 q_1 q_2 - q_0 q_1 + q_2 + 1
>>> result[0].energy
1.0
>>> result[0].values
{2: 0, 1: 1, 0: 0}
>>> result[0].is_feasible
True

If no solution satisfying the constraint is found, the length of the resulting SolverResult will be 0. The following example confirms this by imposing contradictory constraints.

from amplify import BinarySymbolGenerator, Solver
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1
c1 = equal_to(q[0] + q[1], 1)  # Constraint : q[0] + q[1] == 1
c2 = equal_to(q[0] + q[1], 2)  # Constraint : q[0] + q[1] == 2 (Contradicting to c1)

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

model = f + c1 + c2
solver = Solver(client)
result = solver.solve(model)

>>> result[0]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError
>>> len(result)
0

The above function to filter out the infeasible solutions can be disabled by setting filter_solution to False in the solver class.

solver.filter_solution = False
result = solver.solve(model)

>>> len(result)
1
>>> result[0].energy
0.0
>>> result[0].values
{2: 0, 1: 1, 0: 1}
>>> result[0].is_feasible
False

The attribute is_feasible of the obtained solution is False, which means it is not a feasible solution (at least one of the constraints is not satisfied).

You can check which constraints are not met by giving an array of variables to check_constraints().

>>> model.check_constraints(result[0].values)
[((q_0 + q_1 == 1, 1), False), ((q_0 + q_1 == 2, 1), True)]

This means that the first solution in the result list satisfies the constraint condition for q_0 + q_1 == 2.000000 and not for q_0 + q_1 == 1.000000.

Filter Constraints

As in the above example, when we did not find any feasible solution, filter_solution and check_constraints() method can be used to check which of the constrains did not satisfy the condition. However, it is difficult to distinguish the meaning of each constraint condition using only print.

To work around this problem, we next introduce how to determine which of the constraint conditions are satisfied or not by labeling constraints (see Label Constraints).

The following example shows how to filter a one-hot constraint and check if the constraint is satisfied.

from amplify import BinarySymbolGenerator, Solver
from amplify.constraint import one_hot, less_equal, greater_equal
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3, 3)  # Create 3x3 variable array
f = 5 * q.sum() # Objective function
c0 = sum(one_hot(q[i], label=f"one_hot_r{i}") for i in range(3))  # One-hot constraints on all rows
c1 = sum(one_hot(q[:, i], label=f"one_hot_c{i}") for i in range(3))  # One-hot constraints on all columns
c2 = one_hot(q.diagonal(), label=f"one_hot_d")  # One-hot constraints on diagonal direction

model = f + c0 + c1 + c2

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

solver = Solver(client)
solver.filter_solution = False  # Turn off constraint filter
result = solver.solve(model)

It turns out that some of the constraints are not satisfied as can be seen below.

>>> model.check_constraints(result[0].values)
[((one_hot_r0: q_0 + q_1 + q_2 == 1, 1), False),
 ((one_hot_r1: q_3 + q_4 + q_5 == 1, 1), False),
 ((one_hot_r2: q_6 + q_7 + q_8 == 1, 1), True),
 ((one_hot_c0: q_0 + q_3 + q_6 == 1, 1), False),
 ((one_hot_c1: q_1 + q_4 + q_7 == 1, 1), False),
 ((one_hot_c2: q_2 + q_5 + q_8 == 1, 1), True),
 ((one_hot_d: q_0 + q_4 + q_8 == 1, 1), True)]

Using label, for instance, it is possible to extract only the one-hot constraints on rows that do not satisfy the constraint conditions as follows:

>>> [c for c, r in model.check_constraints(result[0].values) if r is False and "one_hot_r" in c.label]
[(one_hot_r0: q_0 + q_1 + q_2 == 1, 1), (one_hot_r1: q_3 + q_4 + q_5 == 1, 1)]

In this way, flexible processing is possible, such as identifying which of constraint conditions are not met and retrying by changing the weight of constraint terms. In the above example, all constraint conditions may be satisfied by increasing the weight of the extracted constraint terms and re-executing.

Sort the Solution

The solutions of the logical model and the input model are sorted in ascending order of energy value. This feature is applicable when the client outputs multiple solutions in a single run. This feature is enabled by default. When sorted, the first element of the execution result, obtained by solve() method, is the best solution. If turned off, the order in which multiple solutions are stored depends on the output order of the machine.

from amplify import Solver
from amplify.client import FixstarsClient

client = FixstarsClient()
solver = Solver(client)
solver.sort_solution = False  # Not sorting multiple solutions (processed in the order of machine output)

Eliminate Duplicate Solutions

When duplicates occur in the solutions, such duplicates are eliminated. This feature is enabled by default. The background of how this feature is implemented in the solver class is explained below.

Note

Normally, it is not necessary to turn off the deduplication feature. This feature is prepared for debugging the output of the Ising machines and the interpretation process of the solution performed by the solve class.

For example, for the inequality constraint less_equal(), disabling deduplicate may result in duplicate output solutions, as shown below.

from amplify import BinarySymbolGenerator, BinaryQuadraticModel, Solver
from amplify.constraint import less_equal
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(4)
f = 4 * q[0] + 3 * q[1] + 2 * q[2] + q[3]
g = less_equal(f, 3)

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second
client.parameters.outputs.duplicate = True  # Consider solutions with the same energy value as different solutions

model = BinaryQuadraticModel(g)
solver = Solver(client)
solver.deduplicate = False  # Distinguish duplicate solutions
result = solver.solve(model)

>>> [f"energy = {s.energy}, q = {decode_solution(q, s.values)}, frequency = {s.frequency}" for s in result]
['energy = 0.0, q = [0., 0., 0., 0.], frequency = 1',
 'energy = 0.0, q = [0., 0., 0., 1.], frequency = 1',
 'energy = 0.0, q = [0., 0., 0., 1.], frequency = 1',
 'energy = 0.0, q = [0., 0., 0., 1.], frequency = 1',
 'energy = 0.0, q = [0., 0., 1., 0.], frequency = 1',
 'energy = 0.0, q = [0., 0., 1., 0.], frequency = 1',
 'energy = 0.0, q = [0., 0., 1., 0.], frequency = 1',
 'energy = 0.0, q = [0., 0., 1., 1.], frequency = 1',
 'energy = 0.0, q = [0., 1., 0., 0.], frequency = 1']

Note

The default behavior of the Amplify Annealing Engine is to output only one solution per energy value, without distinguishing the solutions having the same energy value. Setting client.parameters.outputs.duplicate = True will change this behavior so that all the solutions having the same energy value are distinguished, and all the distinct solutions found in the calculations will be output.

Based on the output of the Ising machine, the solver class takes the reverse steps of executing the problem and interprets the solution in each layer of the physical model, logical model, and input model. At this time, there is a possibility that the solutions would have duplicates, so the solver class implements the process of checking and collecting the duplicate solutions. The followings are the reasons why the identical solutions are output multiple times:

Duplicates on the output solutions of the Ising machines (physical model solutions)
Duplicates on the solution obtained by decoding physical model solutions by logical model (logical model solutions)
Duplicates on the solutions obtained by decoding logical model solutions by input model (solver output)

The first factor is based on the settings and specifications of a given Ising machine. Depending on machines, there can be a case that solutions are output without collecting duplicate solutions. For the latter two, duplication may occur when graph embedding is used in a physical model, or when formulation with auxiliary variables is used in a logical model.

For example, the third factor applies to the case where the Amplify Annealing Engine is used for the above inequality constraints. In other words, as a result of using auxiliary variables in the formulation of inequality constraints, some of the distinct solutions in the logical model including the auxiliary variables become identical if the auxiliary variables are excluded in the output model, which is why some duplications may occur.

For example, in the above case of inequality constraint, the third factor applies when the Amplify Annealing Engine is used, since auxiliary variables are used to formulate the inequality constraint. Although there is no duplicate as interpreting solutions including auxiliary variables in the logical model, duplications occur in the result without the auxiliary variables because the output solutions do not contain the auxiliary variables.

When the deduplication feature of the solver class is turned on, the output will appear as follows:

solver.deduplicate = True  # Combine duplicate solutions (default behavior)
result = solver.solve(model)

>>> [f"energy = {s.energy}, q = {q.decode(s.values)}, frequency = {s.frequency}" for s in result]
['energy = 0.0, q = [0, 0, 0, 0], frequency = 1',
 'energy = 0.0, q = [0, 0, 0, 1], frequency = 3',
 'energy = 0.0, q = [0, 0, 1, 0], frequency = 3',
 'energy = 0.0, q = [0, 0, 1, 1], frequency = 1',
 'energy = 0.0, q = [0, 1, 0, 0], frequency = 1']

Duplicate solutions are put together, and the number of such duplicate solutions can be checked by frequency.

Internal of the Solver Class

Inside the solver class, the following steps are used to execute the Ising machine and output the solution:

Give the solver class an Ising machine client object.
Accept an input model or logical model.
Convert logical model to physical model based on hardware specification.
- For Ising machines with sparsely connected graphs, graph embedding is implemented.
Give the physical model to the client and execute it.
Convert the solution of the physical model into the solution of the logical model.
- Resolve the conditions on physical variables due to the graph embedding.
Filter the solutions of the logical model by checking the constraints.
Convert the filtered logical model solutions to input model solutions.

Of these, the solution of the physical model returned by the client and the solution of the logical model before filtering the constraints can be obtained after executing the solve() method as follows.

from amplify import BinaryPoly, BinarySymbolGenerator, Solver
from amplify.constraint import one_hot
from amplify.client.ocean import DWaveSamplerClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1
c = equal_to(q[0] + q[1], 1)  # Constraint : q[0] + q[1] == 1

client = DWaveSamplerClient()
client.solver = "Advantage_system6.3"
client.token = "XXXX-xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.num_reads = 100  # Number of times executed

solver = Solver(client)
solver_result = solver.solve(f + c)

# Get logical model solution
logical_result = solver.logical_result
# Get physical model solution
client_result = solver.client_result

>>> [f"energy = {s.energy}, client_result  = {s.values}" for s in client_result[:1]]
['energy = 1.0, client_result  = [0, 0, 1, 0, 0, 0, 1, 0, 3, 3, 3, ...]']
>>> [f"energy = {s.energy}, logical_result = {s.values}" for s in logical_result[:1]]
['energy = 1.0, logical_result = [0, 0, 1, 0]']
>>> [f"energy = {s.energy}, solver_result  = {s.values}" for s in solver_result[:1]]
['energy = 1.0, solver_result  = [0, 1, 0]']

WIP

The interface to get the progress of the output solution is subject to change in the future.

In logical_result, the decoded solution for logical model (logical_model_poly) is stored as LogicalResult object.

The output results of the Ising machines are stored in client_result. The class of these object depends on the used client because the outputs follow their specifications. Please refer to “Execution result class” of each client in Client for more information.

Execution Time Information

After executing solve(), the execution time can be obtained by the execution_time property. This property returns the elapsed time it took the machine to find the solutions in the unit of milliseconds.

Below is the example of obtaining the execution time of FixstarsClient.

from amplify import BinaryPoly, BinarySymbolGenerator, Solver
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1
c = equal_to(q[0] + q[1], 1)  # Constraint: q[0] + q[1] == 1

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

solver = Solver(client)
solver_result = solver.solve(f + c)

>>> solver.execution_time
969

It can be seen that the execution time is close to the specified timeout value.

Obtain Execution Information Specific to the Machine

After executing solve(), machine specific information on execution can be obtained by client_result. The returned object is an instance of the execution result class of the client (found in Client).

Although different information may be returned depending on machines, the execution time information can be obtained in common by timing from each client result class. The returned object is an instance of the execution time class of the client (found in Client). The kind of information and unit of time included in the execution time class follow the API specification of each client. For instance, the Fixstars AE uses milliseconds, D-Wave uses microseconds, and Fujitsu uses seconds.

Below is an example of obtaining the execution information of FixstarsClient.

from amplify import BinaryPoly, BinarySymbolGenerator, Solver
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(3)
f = 2 * q[0] * q[1] * q[2] - q[0] * q[1] + q[2] + 1
c = equal_to(q[0] + q[1], 1)  # 制約: q[0] + q[1] == 1

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000  # Timeout is 1 second

solver = Solver(client)
solver_result = solver.solve(f + c)
client_result = solver.client_result

>>> client_result.timing.cpu_time
107.565479
>>> client_result.timing.queue_time
83.35885699999992
>>> client_result.timing.time_stamps
[38.904337]
>>> client_result.execution_parameters.num_iterations
28

Note

[Deprecated] annealing_time_ms became deprecated from v0.7.0. Please use execution_time to obtain the execution time in milliseconds.

Embedding into Physical Graphs

The solver class automatically performs graph embedding of input models and logical models into physical models as needed. More specifically, when client is HitachiClient, DWaveClient or DWaveSamplerClient, graph embedding will be performed.

In this case, a logical variable is represented by a set of several physical variables (chains) to implement interactions between the logical variables. In order for the physical variables in a chain to have the same value, an interaction between each pair of the physical variables in the chain is applied. The magnitude of the interaction is called the chain weight (or chain strength).

The solver class will automatically adjust the chain weight, but you can also change the chain strength manually with chain_strength. Furthermore, if the number of logical variables exceed the limit size of embedding into a fully connected graph, the solver class will dynamically search a graph embedding. The time limit to perform this searching can be set by embedding_time_limit. These properties should by set before calling the solve() method.

from amplify import Solver
from amplify.client.ocean import DWaveSamplerClient

client = DWaveSamplerClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.solver = "Advantage_system4.1"
client.parameters.num_reads = 100

solver = Solver()
solver.client = client
solver.chain_strength = 2.0          # default: 1.0
solver.embedding_time_limit = 2000   # default: 1000ms