# 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 {py:func}`~amplify.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.

```{image} ../_images/conversion_intermediate_light.drawio.svg
:width: 70%
:align: center
:class: only-light
```

```{image} ../_images/conversion_intermediate_dark.drawio.svg
:width: 70%
:align: center
:class: only-dark
```

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.

```{image} ../_images/conversion_embedding_light.drawio.svg
:width: 90%
:align: center
:class: only-light
```

```{image} ../_images/conversion_embedding_dark.drawio.svg
:width: 90%
:align: center
:class: only-dark
```

(create-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 {py:class}`~amplify.FixstarsClient`.

```{testcode}
from amplify import FixstarsClient

client = FixstarsClient()
```
```{doctest}
>>> 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 {py:class}`~amplify.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 "[](solvers.md)" for more information.
```

The Amplify SDK then performs the conversion to an intermediate model as follows.

```{card} Steps for the intermediate model construction
:shadow: md
:class-card: sd-border-2 sd-my-3

1.  Verify that the Amplify SDK can convert the objective function to a form the solver can handle by performing variable conversion and order reduction.
2.  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.
3.  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.
4.  If the Amplify SDK can convert the objective function and all constraint conditions, perform variable transformation and order reduction.
5.  Delete unused variables and reconstruct variables and model
6.  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 {bdg-warning}`Graph` in [the solver client list](#solver-clients).

First, the Amplify SDK obtains the solver-specific graph structure from the solver client. The following is an example of the {py:class}`~amplify.DWaveSamplerClient`.

```{testcode}
from amplify import DWaveSamplerClient

client = DWaveSamplerClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
```

```{doctest}
>>> graph = client.graph # Graph structure of DWaveSampler # doctest: +SKIP
>>> graph.type # doctest: +SKIP
'Pegasus'
>>> len(graph.nodes) # doctest: +SKIP
5627
>>> len(graph.edges) # doctest: +SKIP
40279
```

The graph structure of the solver corresponding to {py:class}`~amplify.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.

```{card} Graph embedding procedure
:shadow: md
:class-card: sd-border-2 sd-my-3

1.  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.
2.  Perform graph embedding from the graph representation of the unconstrained intermediate model's objective function into a solver-specific graph (physical graph).
3.  Create a correspondence map (chain) of variables between the intermediate model and the physical graph.
4.  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 {py:func}`~amplify.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 {py:attr}`~amplify.Result.solutions` attribute.

The {py:func}`~amplify.solve` function stores information about the series of transformations and inverse transformations and the results of the solver execution in the returned {py:attr}`~amplify.Result` class. The following are attributes of the {py:attr}`~amplify.Result` class that provide typical information.

```{list-table}
:width: 100%
:header-rows: 1
:widths: 3 3 6 1

* - Attribute
  - Data type
  - Summary
  - Details
* - {py:attr}`~amplify.Result.solutions`
  - {py:attr}`~amplify.Result.SolutionList`
  - Stores information such as solutions of the input model and values of the objective function.
  - [{octicon}`link`](#result-info-on-solutions)
* - {py:attr}`~amplify.Result.intermediate`
  - {py:attr}`~amplify.Result.ModelConversion`
  - Stores intermediate model and its variable conversion information.
  - [{octicon}`link`](#intermediate-result)
* - {py:attr}`~amplify.Result.embedding`
  - {py:class}`~amplify.Result.GraphConversion`
  - Stores graph embedding information from the intermediate model to the physical graph (only if graph embedding is required).
  - [{octicon}`link`](#embedding-result)
* - {py:attr}`~amplify.Result.client_result`
  - `Client.Result`
  - Stores solver client execution results.
  - [{octicon}`link`](#client-solve)
```

```{seealso}
For more information about the intermediate model and graph embedding run results, see [](intermediate.md) and [](graph.md).
```

(conversion-parameters)=

## Model conversion parameters

The parameters used in model transformations are listed below. The {py:func}`~amplify.solve` function can take these parameters as keyword arguments.

```{list-table}
:header-rows: 1
:width: 100%
:widths: 3 3 6 1

* - Parameter name
  - Type of model conversion
  - Summary
  - Details
* - `integer_encoding_method`
  - Variable conversion
  - Algorithm to convert integer variables to binary variables
  - [{octicon}`link`](#encode-integer)
* - `quadratization_method`
  - Degree reduction
  - Algorithm for degree reduction
  - [{octicon}`link`](#quadratization-method)
* - `substitution_multiplier`
  - Degree reduction
  - Constraint weights generated by degree reduction
  - [{octicon}`link`](#substitution-multiplier)
* - `embedding_method`
  - Graph embedding
  - Algorithm used for graph embedding
  - [{octicon}`link`](#embedding-method)
* - `embedding_timeout`
  - Graph embedding
  - Graph embedding timeout value (in seconds)
  - [{octicon}`link`](#embedding-timeout)
* - `chain_strength`
  - Graph Embedding
  - Graph embedding parameters for polynomial expressions.
  - [{octicon}`link`](#chain-strength)
```

For example, the following example sets the algorithm used to convert integer variables to binary variables in the {py:func}`~amplify.solve` function to {py:class}`~amplify.IntegerEncodingMethod.Unary`,

```{testcode}
:hide:
from amplify import solve, Model, FixstarsClient

model = Model()
client = FixstarsClient()
```

```{testcode}
result = solve(model, client, integer_encoding_method="Unary")
```

The following parameters also specify the penalty generation method for inequality constraints. When constructing a {py:class}`~amplify.Constraint` object representing an inequality constraint using a helper function such as {py:func}`~amplify.less_equal` or the {py:class}`~amplify.Constraint` class constructor, you can use the argument `method` keyword to specify the method.

```{list-table}
:header-rows: 1
:width: 100%
:widths: 3 3 6 1

* - Parameter name
  - Type of model conversion
  - Summary
  - Details
* - `penalty_formulation`
  - Penalty generation
  - Penalty generation algorithm
  - [{octicon}`link`](#ineq-penalty)
```

For example, the following example sets the algorithm used to generate the penalty for an inequality constraint to an {py:class}`~amplify.PenaltyFormulation.IntegerVariable` in the {py:func}`~amplify.solve` function.

```{testcode}
:hide:
from amplify import VariableGenerator, less_equal
q = VariableGenerator().array("Binary", 3)
```

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

(conversion-next-step)=

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

`````{grid} 1
:gutter: 3
````{grid-item-card} Variable conversion and degree reduction
:link: intermediate
:link-type: doc
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.
```{div} sd-text-right
[Learn more »](intermediate.md)
```
````
````{grid-item-card} Constraints and penalties
:link: penalty
:link-type: doc
This page describes how the Amplify SDK generates penalty functions for solvers that cannot directly handle constraints.
```{div} sd-text-right
[Learn more »](penalty.md)
```
````
````{grid-item-card} Graph embedding
:link: graph
:link-type: doc
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.
```{div} sd-text-right
[Learn more »](graph.md)
```
````
`````

```{toctree}
:hidden:
intermediate.md
penalty.md
graph.md
```