Model Conversions#
The Amplify SDK allows you to create models that contain real and integer variables and polynomials of any degree. On the other hand, combinatorial optimization solvers are generally limited in the types and degrees of variables they can handle, the types of constraints the solver can accept, or whether they can take constraints directly, and they may only accept second-order polynomials with a specific structure.
When a model that the solver cannot directly handle is fed to the solve() function, the Amplify SDK performs the conversion process into a form that the solver can take as automatically as possible. Specifically, the Amplify SDK performs variable conversions, degree reductions, and other model conversions, as well as graph embedding, which converts a second-order polynomial into a form that the solver can accept and then runs the solver.
Overview of the conversion process#
First, Amplify SDK performs variable conversion and order reduction according to the types of variables the solver can handle and the order of the objective function and constraints. The model after variable conversion and order reduction is called the intermediate model. When the intermediate model is in a form that can be input to the solver, the Amplify SDK asks the solver to solve the intermediate model. The solution returned by the solver is the inverse of the variable conversions performed on the input model, and the Amplify SDK evaluates the solution of the input model.
Depending on the solver type, the solver may not take the intermediate model directly. This is due to the limitation of second-order terms that the solver can take and the limitation of variable type and order. In this case, the Amplify SDK performs an additional operation called graph embedding to convert the intermediate model into a form that can be input to the solver. The Amplify SDK computes the solution of the intermediate model by applying the inverse transformation of the graph embedding performed on the intermediate model to the solution returned by the solver. In addition, the Amplify SDK obtains the solution of the input model by applying the inverse transformation of the variable transformation performed on the input model to the solution of the intermediate model.
Intermediate model construction#
In preparation for the conversion process, the following information is obtained from the solver client to determine the types of problems the solver can handle and the degree of the objective function and constraints of the intermediate model to be output.
Types of variables for the objective functions and their respective degrees
Types of variables for the equality constraints and their respective degrees
Types of variables for the inequality constraints and their respective degrees
The Amplify SDK yields the maximum degree the solver can handle for each variable type. Below is an example for FixstarsClient.
from amplify import FixstarsClient
client = FixstarsClient()
>>> client.acceptable_degrees.objective # degree for the objective function
{Binary: Quadratic, Ising: Zero, Integer: Zero, Real: Zero}
>>> client.acceptable_degrees.equality_constraints # degree for the equality constraints
{Binary: Zero, Ising: Zero, Integer: Zero, Real: Zero}
>>> client.acceptable_degrees.inequality_constraints # degree for the inequality constraints
{Binary: Zero, Ising: Zero, Integer: Zero, Real: Zero}
In FixstarsClient, we see that the objective function is limited to the second order of the binary variable and that the solver cannot handle equality and inequality constraints directly.
Note
The degree that the solver can handle varies from client to client and also depends on the solver’s client settings. See “Client details” for more information.
The Amplify SDK then performs the conversion to an intermediate model as follows.
Verify that the Amplify SDK can convert the objective function to a form the solver can handle by performing variable conversion and order reduction.
Verify that the Amplify SDK can convert equality and inequality constraints to a form that the solver can handle by performing variable conversion and order reduction.
If there are constraints that the solver cannot handle, calculate their penalty functions and check if the penalty functions can be converted to the same conditions as the objective function by performing variable conversion and order reduction.
If the Amplify SDK can convert the objective function and all constraint conditions, perform variable transformation and order reduction.
Delete unused variables and reconstruct variables and model
Create a variable conversion map between the input model and the intermediate model.
Graph Embedding#
For solvers that require graph embedding, the Amplify SDK performs graph embedding in addition to conversion to an intermediate model. Whether graph embedding is needed is determined on a solver-by-solver basis, and solvers that require graph embedding are labeled Graph in the solver client list.
First, the Amplify SDK obtains the solver-specific graph structure from the solver client. The following is an example of the DWaveSamplerClient.
from amplify import DWaveSamplerClient
client = DWaveSamplerClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
>>> graph = client.graph # Graph structure of DWaveSampler
>>> graph.type
'Pegasus'
>>> len(graph.nodes)
5627
>>> len(graph.edges)
40279
The graph structure of the solver corresponding to DWaveSamplerClient is a Pegasus graph with 5627 nodes and 40279 edges.
The Amplify SDK uses the following procedure to perform graph embedding on a second-order polynomial so that the solver can handle it.
Convert the intermediate model to an optimization problem consisting of only one objective function (unconstrained intermediate model) by adding the penalty function of each constraint in the intermediate model to the objective function.
Perform graph embedding from the graph representation of the unconstrained intermediate model’s objective function into a solver-specific graph (physical graph).
Create a correspondence map (chain) of variables between the intermediate model and the physical graph.
Based on the chain, transform the polynomial obtained in 1. to the polynomial in a form that the solver can handle.
Running the solver and getting results#
The model transformation and graph embedding described above have converted the model into a format that can be input to the solver. The Amplify SDK then calls the solve method on the solver client using the solve() function to perform optimization. The solver client does everything from creating the request data the solver needs to calling the API and optimization functions and analyzing the solver response.
The Amplify SDK performs the inverse conversion of each variable conversion process in the graph embedding and intermediate model construction step by step on the solution returned by the solver, obtaining the solution of the input model and storing it in the solutions attribute.
The solve() function stores information about the series of transformations and inverse transformations and the results of the solver execution in the returned Result class. The following are attributes of the Result class that provide typical information.
Attribute |
Data type |
Details |
|---|---|---|
Stores information such as solutions of the input model and values of the objective function. |
||
Stores intermediate model and its variable conversion information. |
||
Stores graph embedding information from the intermediate model to the physical graph (only if graph embedding is required) |
||
|
Stores solver client execution results |
See also
For more information about the intermediate model and graph embedding run results, see Variable Conversion and Degree Reduction and Graph Embedding.
Model conversion parameters#
The parameters used in model transformations are listed below. The solve() function can take these parameters as keyword arguments.
Parameter name |
Type of model conversion |
Summary |
Details |
|---|---|---|---|
|
Variable conversion |
Algorithm to convert integer variables to binary variables |
|
|
Degree reduction |
Algorithm for degree reduction |
|
|
Degree reduction |
Constraint weights generated by degree reduction |
|
|
Graph embedding |
Algorithm used for graph embedding |
|
|
Graph embedding |
Graph embedding timeout value (in seconds) |
|
|
Graph Embedding |
Graph embedding parameters for polynomial expressions. |
For example, the following example sets the algorithm used to convert integer variables to binary variables in the solve() function to Unary,
result = solve(model, client, integer_encoding_method="Unary")
The following parameters also specify the penalty generation method for inequality constraints. When constructing a Constraint object representing an inequality constraint using a helper function such as less_equal() or the Constraint class constructor, you can use the argument method keyword to specify the method.
Parameter name |
Type of model conversion |
Summary |
Details |
|---|---|---|---|
|
Penalty generation |
Penalty generation algorithm |
For example, the following example sets the algorithm used to generate the penalty for an inequality constraint to an IntegerVariable in the solve() function.
le_constraint = less_equal(
q[0] + q[1] + q[2], 2, penalty_formulation="IntegerVariable"
)
Next step#
For those interested in learning more the conversion process, the following pages explain the model conversion process, the implementation of constraints by generating penalty functions, and the graph embedding process performed by the Amplify SDK.