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 secondorder 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 secondorder 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 secondorder 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
{VariableType.Binary: Degree.Quadratic, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}
>>> client.acceptable_degrees.equality_constraints # degree for the equality constraints
{VariableType.Binary: Degree.Zero, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}
>>> client.acceptable_degrees.inequality_constraints # degree for the inequality constraints
{VariableType.Binary: Degree.Zero, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.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 solverbysolver basis, and solvers that require graph embedding are labeled Graph in the solver client list.
First, the Amplify SDK obtains the solverspecific 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 secondorder 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 solverspecific 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 
Summary 
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.