Solver

This section describes the solver for the logical model.

Constructing a Solver Object

The solver class abstracts the hardware by including the clients of the Ising machines, 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 and solve Ising machines with a unified interface.

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

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

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_system1.1"
client.num_reads = 100

solver = Solver()
solver.client = client
solver.chain_strength = 2.0

Running the Solver and Obtaining the Solution

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

Input Model

For the input model, the following inputs can be made.

Polynomial

Polynomials, including third-order and higher, can be entered.

Matrix

Matrix representations of quadratic polynomials can be entered. The 2nd argument represents the constant term.

Constraint

Constraint objects can be entered.

Logical model

The following inputs are available for the logical model:

Example

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

  • solutions : Obtain a list of execution results. Each element has the following attributes.

    • energy : Obtain the energy value (evaluation value of the input model).

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

    • frequency : Obtain the number of identical solutions.

    • is_feasible : Return whether the solution satisfies all constraints.

  • __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.

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

q = gen_symbols(BinaryPoly, 8)
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 is 1 second

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

Solution Filtering

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 BinaryPoly, gen_symbols, Solver
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 8)
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

model = f + c
solver = Solver(client)
result = solver.solve(model)
>>> f
2.000000 q_0 q_1 q_2 - q_0 q_1 + q_2 + 1.000000
>>> [f"energy = {s.energy}, q[0] = {s.values[0]}, q[1] = {s.values[1]}, q[2] = {s.values[2]}, is_feasible = {s.is_feasible}" for s in result]
['energy = 1.0, q[0] = 0, q[1] = 1, q[2] = 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 BinaryPoly, gen_symbols, Solver
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 8)
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 (Contradictory 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)
>>> f
2.000000 q_0 q_1 q_2 - q_0 q_1 + q_2 + 1.000000
>>> [f"energy = {s.energy}, q[0] = {s.values[0]}, q[1] = {s.values[1]}, q[2] = {s.values[2]}, is_feasible = {s.is_feasible}" for s in result]
[]

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)
>>> [f"energy = {s.energy}, q[0] = {s.values[0]}, q[1] = {s.values[1]}, q[2] = {s.values[2]}, is_feasible = {s.is_feasible}" for s in result]
['energy = 1.0, q[0] = 1, q[1] = 0, q[2] = 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.000000, 1), True), ((q_0 + q_1 == 2.000000, 1), False)]

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

It is possible to filter 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 BinaryPoly, gen_symbols, sum_poly
from amplify.constraint import equal_to, less_equal, greater_equal

q = gen_symbols(BinaryPoly, 3, 3)
f = - q[0][0] - q[1][1] - q[2][2]
one_hot = sum(equal_to(sum_poly(q[i]), 1, f"one_hot_{i}") for i in range(3)) # One-hot constraint on the direction of travel
c1 = less_equal(q[0][0] + q[1][0], 1, "less_equal")  # Constraint : q[0][0] + q[1][0] <= 1
c2 = greater_equal(q[1][2] + q[2][2], 1, "greater_equal")  # Constraint : q[2][2] + q[3][2] >= 1

model = f + one_hot + c1 + c2
>>> solution = [1, 1, 0, 0, 1, 1, 0, 0, 1]
>>> model.check_constraints(solution)
[((one_hot_0: q_0 + q_1 + q_2 == 1.000000, 1), False), ((one_hot_1: q_3 + q_4 + q_5 == 1.000000, 1), False), ((one_hot_2: q_6 + q_7 + q_8 == 1.000000, 1), False), ((less_equal: q_0 + q_3 <= 1, 1), True), ((greater_equal: q_5 + q_8 >= 1, 1), True)]

In this example, there are only a few constraints, so it is easy to check them. However, if there are many constraints, it is time-consuming to check them one by one. By appropriately labeling constraints, it helps to check the constraints in an organized manner.

Let us see the example of checking the one-hot constraints above. Since the one-hot constraints are labeled one_hot_0, one_hot_1, and one_hot_2 above, we can filter them based on those labels. Below, we filter out the one-hot constraints by using regular expressions for the labels from the ones that satisfy the constraints and the ones that do not.

>>> import re
>>> unsat_one_hot = [(c, b) for (c, b) in model.check_constraints(solution) if not b and re.match('one_hot_[0-9]+', c.label)]
>>> unsat_one_hot
[((one_hot_0: q_0 + q_1 + q_2 == 1.000000, 2), False), ((one_hot_1: q_3 + q_4 + q_5 == 1.000000, 2), False)]
>>> sat_one_hot = [(c, b) for (c, b) in model.check_constraints(solution) if b and re.match('one_hot_[0-9]+', c.label)]
>>> sat_one_hot
[((one_hot_2: q_6 + q_7 + q_8 == 1.000000, 2), True)]
>>> print(f"unsatisfied: {len(unsat_one_hot)}, satisfied: {len(sat_one_hot)}")

This result shows that there are two one-hot constraints that are not satisfied and one that is satisfied. If the solution obtained from the Ising machine does not satisfy the constraints, it is generally because the strength of the constraints is not large enough. We can thus double the strength of the one-hot constraint to see how the result changes. As before, we will use regular expressions to extract and manipulate one-hot constraints on labels.

>>> for c in model.input_constraints:
>>>     if re.match('one_hot_[0-9]+', c.label):
>>>         c[1] *= 2
>>> model.input_constraints
[(one_hot_0: q_0 + q_1 + q_2 == 1.000000, 2), (one_hot_1: q_3 + q_4 + q_5 == 1.000000, 2), (one_hot_2: q_6 + q_7 + q_8 == 1.000000, 2), (less_equal: q_0 + q_3 <= 1, 1), (greater_equal: q_5 + q_8 >= 1, 1)]

You can see that the weight factor is doubled only for the one-hot constraint.

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.

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

from amplify import BinaryPoly, gen_symbols, Solver, decode_solution
from amplify.constraint import equal_to
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 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.

The followings are the reasons why the identical solutions are output multiple times:

  • There are duplicates on the solutions in the first place due to the specifications of the Ising machine outputs

  • Identical output solutions are different on the level of the physical model

  • Identical output solutions are different on the level of the logical model

The first factor is based on the configuration and operating specifications of a given Ising machine. For the latter two, it means that duplication may occur when “graph embedding” is used in the physical model, or when “formulation with auxiliary variables” is used in the 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.

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 = {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 = 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.

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 is enabled by default. 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  # Do not sort multiple solutions (process in machine output order)

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 equal_to
from amplify.client.ocean import DWaveSamplerClient

q = gen_symbols(BinaryPoly, 8)
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)
logical_result = solver.logical_result
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.