Solver

This section describes the solver for the logical model.

See also

Before reading this section, please check the basic usage of Amplify SDK in Tutorial, polynomial object in Polynomial, and constraint object in Constraint.

For more information on the client objects, which are used in the following explanations, see Client.

The solver class abstracts the hardware by including the Ising machine clients, and provides an interface for solving input and logical models. By using the solver class, it is no longer necessary to be aware of the differences in the specifications of various Ising machines, and it is possible to execute the Ising machines and find solutions in a unified interface.

Constructing a Solver Object

The solver is constructed using the 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

See also

See Client for details of the client classes and available parameters.

Running the Solver and Obtaining the Solution

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

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

It is also possible to give polynomial, matrix, and constraint objects to solve() method. In this case, a logical model is automatically created accordingly to the type of given object. This is meant to be a simple method, and the combination of objective functions and constraint conditions will not be given. To work around this issue, a logical model object should be explicitly constructed, or use addition operator of 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.

To use constraint objects, the following arguments are given:

Example

Execution results will be returned as solve() method is executed. The following is the example of 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 : Obtains a list of execution results. Each element has the following attributes.

    • energy : Obtains the energy value (evaluated value of the input model).

    • values : Obtains the value of an input variable as a list.

    • frequency : Obtains the number of identical solutions.

    • is_feasible : Returns whether the solution satisfies all constraints. By filtering solutions, only solutions with True are stored by default.

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

  • __getitem__ : Return the element access solutions[n] of solutions transparently.

  • __len__ : Return the number of elements in solutions transparently, len(solutions).

  • __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, the solutions are filtered in such a way that only feasible solutions are given if constraint conditions are given. If the length of result is 0, it indicates that no solution satisfying the constraints is found.

Filtering Solution

When 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 sequence obtained satisfies the constraint condition for q_0 + q_1 == 1.000000 and not for q_0 + q_1 == 2.000000.

Filtering Constraints

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

To work around this problem, we next introduce the method of determining whether to see which of the constraint conditions are satisfied or not by filtering constraints based on the label given by Labeling 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)]

By 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.

Sorting 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)

Elimination of Duplicate Solutions

When duplicates occur in the solution sequences of logical models or input models, such duplicates are eliminated. This 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 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 will be duplicated, 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 operating 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 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.

Inside the Solver Class

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

  1. Give the solver class an Ising machine client object.

  2. Accept an input model or logical model.

  3. Convert logical model to physical model based on hardware specification

    • For Ising machines with sparsely connected graphs, graph embedding is implemented

  4. Give the physical model to the client and execute it

  5. Convert the solution of the physical model into the solution of the logical model

    • Resolve the constraints on physical variables due to the graph embedding

  6. Filter the solutions of the logical model by checking the constraints

  7. 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, gen_symbols, 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 = "DW_2000Q_VFYC_6"
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 given in client_result. The classes of these objects are different depending on clients since they have the outputs of the machines as they are. Please refer to “Execution result class” of each client in Client for more information.

Execution Time Information

After executing solve(), machine specific information of execution can be obtained by client_result. Although different information may be returned depending on machines, one of the common information is execution time.

Each client’s execution result class (found in Client) has, in common, the property to obtain the Ising machine’s execution time (annealing_time_ms). This property returns the time that took to find solutions in the unit of milliseconds from the information of the execution time that each client has.

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

from amplify import BinaryPoly, gen_symbols, 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)
client_result = solver.client_result
>>> client_result.annealing_time_ms
969

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

Details of execution time information can be obtained from timing. The returned object can be found in each client’s execution time class (found in Client). The information and unit of time included in execution time class follow the API specification of each client. For instance, Fixstars AE uses milliseconds, D-Wave uses microseconds, Fujitsu uses seconds.

Below is the example for getting execution time information of FixstarsClient.

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

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 solver.client is HitachiClient, DWaveClient or DWaveSamplerClient, graph embedding will be performed.

In this case, a logical variable is represented by several physical variables (chains). In order for the physical variables in a chain to be aligned in the same direction, an interaction between 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 also automatically adjust the chain weight. You can also change the chain strength as needed.

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