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

solve(

`BinaryQuadraticModel`

)solve(

`IsingQuadraticModel`

)solve(

`BinaryIntQuadraticModel`

)solve(

`IsingIntQuadraticModel`

)

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:

solve(

`BinaryPoly`

)solve(

`IsingPoly`

)solve(

`BinaryIntPoly`

)solve(

`IsingIntPoly`

)

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:

solve(

`BinaryConstraint`

)solve(

`BinaryConstraintTerm`

)solve(

`BinaryConstraints`

)solve(

`BinaryIntConstraint`

)solve(

`BinaryIntConstraintTerm`

)solve(

`BinaryIntConstraints`

)

### 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:

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 constraints 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, 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
```