Model Conversions¶

The Amplify SDK lets you create models with real and integer variables, and polynomials of any degree. Combinatorial optimization solvers, however, have limits. They restrict the types and degrees of variables they accept, the kinds of constraints they take, and whether they accept constraints at all. Some solvers accept only second-order polynomials with a specific structure.

When solve() receives a model that the solver cannot handle directly, the Amplify SDK converts the model into a form the solver can accept. The conversion includes variable conversion, degree reduction, and graph embedding. Graph embedding converts a second-order polynomial into the form the solver requires. The SDK then runs the solver.

Overview of the conversion process¶

First, the Amplify SDK performs variable conversion and degree reduction based on the variable types the solver supports and the allowed degree of the objective function and constraints. The model after this step is called the intermediate model. When the intermediate model is in a form the solver can accept, the SDK passes it to the solver. The SDK then applies the inverse of the variable conversions to the solver’s solution to obtain the solution of the input model.

_images/conversion_intermediate_light.drawio.svg

_images/conversion_intermediate_dark.drawio.svg

Some solvers cannot accept the intermediate model directly. This happens because the solver limits the number of second-order terms it accepts, in addition to limiting variable type and degree. In that case, the Amplify SDK performs an additional step called graph embedding to convert the intermediate model into a form the solver can accept. The SDK applies the inverse of the graph embedding to the solver’s solution to obtain the solution of the intermediate model. It then applies the inverse of the variable conversions to that solution to obtain the solution of the input model.

_images/conversion_embedding_light.drawio.svg

_images/conversion_embedding_dark.drawio.svg

Intermediate model construction¶

Before the conversion, the SDK reads the following information from the solver client. This information determines what problems the solver can handle and sets the degree of the objective function and constraints in the intermediate model.

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 SDK yields the maximum degree the solver can handle for each variable type. Below is an example for AmplifyAEClient.

from amplify import AmplifyAEClient

client = AmplifyAEClient()

>>> client.acceptable_degrees.objective  # degree for the objective function
{VariableType.Binary: Degree.Quartic, 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.Quartic, 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.Quartic, VariableType.Ising: Degree.Zero, VariableType.Integer: Degree.Zero, VariableType.Real: Degree.Zero}

With AmplifyAEClient, the objective function accepts quartic terms in binary variables. The solver also handles equality and inequality constraints up to fourth order 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 SDK then converts the model 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 SDK performs graph embedding in addition to the intermediate model conversion. Whether graph embedding is needed depends on the solver. Solvers that require it are labeled Graph in the solver client list.

First, the SDK reads the solver-specific graph structure from the solver client. The following is an example for 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 solver that DWaveSamplerClient targets uses a Pegasus graph with 5627 nodes and 40279 edges.

The SDK uses the following procedure to perform graph embedding on a second-order polynomial.

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 transformations and graph embedding above produce a model the solver can accept. The SDK then calls the solve method on the solver client through solve() to run the optimization. The solver client builds the request, calls the API or optimization function, and parses the solver response.

The SDK applies the inverse conversion of each variable conversion step (graph embedding and intermediate model construction) to the solution the solver returns. This produces the solution of the input model, which the SDK stores in the solutions attribute.

The solve() function stores information about the conversions, inverse conversions, and solver execution in the returned Result class. The following attributes of Result give the most common 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 that control model conversion are listed below. Pass them as keyword arguments to solve().

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.

The following example sets the integer-variable-to-binary-variable conversion algorithm to Unary in solve().

result = solve(model, client, integer_encoding_method="Unary")

The following parameter specifies the penalty generation method for inequality constraints. To build a Constraint object for an inequality constraint, use a helper function such as less_equal() or the Constraint constructor. Pass the method with the method keyword argument.

Parameter name	Type of model conversion	Summary	Details
`penalty_formulation`	Penalty generation	Penalty generation algorithm

The following example sets the penalty generation algorithm for inequality constraints to IntegerVariable in solve().

le_constraint = less_equal(
    q[0] + q[1] + q[2], 2, penalty_formulation="IntegerVariable"
)

Next step¶

The following pages explain the conversion process in detail. They cover variable conversion and degree reduction, constraint implementation through penalty functions, and the graph embedding process.

Variable conversion and degree reduction

This page explains how the Amplify SDK performs variable conversions and degree reduction to adapt the model to the variable types and polynomial degree the solver accepts.

Learn more »

Variable Conversion and Degree Reduction

Constraints and penalties

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

Learn more »

Constraints and Penalty Functions

Graph embedding

This page describes the graph embedding process. Some solvers accept only quadratic polynomials with a solver-specific structure. Graph embedding converts an arbitrary model into that form. The page uses D-Wave as an example to explain the graph embedding that the Amplify SDK implements.

Learn more »

Graph Embedding