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.

_images/conversion_intermediate_light.drawio.svg

_images/conversion_intermediate_dark.drawio.svg

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.

_images/conversion_embedding_light.drawio.svg

_images/conversion_embedding_dark.drawio.svg

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.

Steps for the intermediate model construction

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.

Graph embedding procedure

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	Summary
`solutions`	`SolutionList`	Stores information such as solutions of the input model and values of the objective function.
`intermediate`	`ModelConversion`	Stores intermediate model and its variable conversion information.
`embedding`	`GraphConversion`	Stores graph embedding information from the intermediate model to the physical graph (only if graph embedding is required).
`client_result`	`Client.Result`	Stores solver client execution results.

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
`integer_encoding_method`	Variable conversion	Algorithm to convert integer variables to binary variables
`real_encoding_method`	Variable conversion	Algorithm to convert real variables to binary variables
`quadratization_method`	Degree reduction	Algorithm for degree reduction
`substitution_multiplier`	Degree reduction	Constraint weights generated by degree reduction
`embedding_method`	Graph embedding	Algorithm used for graph embedding
`embedding_timeout`	Graph embedding	Graph embedding timeout value (in seconds)
`chain_strength`	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_formulation`	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.

Variable conversion and degree reduction

This page explains how the Amplify SDK performs variable conversions and degree reduction to adapt the model to the type of variables and polynomial degree that the solver can handle.

Learn more »

Variable Conversion and Degree Reduction

Constraints and penalties

This page describes how the Amplify SDK generates penalty functions for solvers that cannot directly handle constraints.

Learn more »

Constraints and Penalty Functions

Graph embedding

This page describes the graph embedding process that allows arbitrary model input when the quadratic polynomial input to the solver has a solver-specific structure. In particular, we will use the D-Wave example to describe graph embedding implemented in the Amplify SDK.

Learn more »

Graph Embedding