# Variable Conversion and Degree Reduction

The Amplify SDK allows you to create models that include real and integer variables and polynomials of any degree. On the other hand, combinatorial optimization solvers are generally limited in the types of variables and degrees of polynomials they can handle. This section describes the variable conversion and degree reduction methods implemented in the Amplify SDK to match the model with the variable types and the polynomial degree that the solver can handle.

## Retrieving an intermediate model

Using the {py:meth}`~amplify.Model.to_intermediate_model` method on a model returns an intermediate model transformed to match the specified variable type and polynomial degree. Since this method is used within the {py:func}`~amplify.solve` function when building the intermediate model, it is helpful to see how the Amplify SDK performs variable conversion and degree reduction.

```{attention}
Usually, there is no need to call the {py:meth}`~amplify.Model.to_intermediate_model` method; use it to see how Amplify SDK performs variable transformations and order reduction within the {py:func}`~amplify.solve` function.
```

You can specify the intermediate model's variable type and polynomial degree in the first argument of the {py:meth}`~amplify.Model.to_intermediate_model` method. If you want to use the degree that the solver can handle, pass the {py:attr}`~amplify.FixstarsClient.acceptable_degrees` property as follows.

```{testcode}
from amplify import VariableGenerator, Model, FixstarsClient, AcceptableDegrees

gen = VariableGenerator()
q = gen.array("Binary", 3)

model = Model(q[0] * q[1] * q[2])

client = FixstarsClient()
client.parameters.timeout = 1000

im, mapping = model.to_intermediate_model(client.acceptable_degrees)
```

The {py:meth}`~amplify.Model.to_intermediate_model` method returns an intermediate model and a map of variable conversions from the input model to the intermediate model.

For example, {py:class}`~amplify.FixstarsClient` can handle a quadratic polynomial of binary variables as an objective function, as seen in "[](#create-intermediate-model)." In the above example, the input model is a cubic polynomial of binary variables, but the {py:meth}`~amplify.Model.to_intermediate_model` method converts the intermediate model's objective function to a quadratic polynomial of binary variables.

```{doctest}
>>> print(im)
minimize:
  q_0 q_1 + q_0 q_2 - q_0 q'_0 + q_1 q_2 - q_1 q'_0 - q_2 q'_0 + q'_0
```

```{note}
The variables in the intermediate model use a different {py:class}`~amplify.VariableGenerator` than the input variables. In other words, it is impossible to operate between variables in the input model and the intermediate model.
```

Passing an instance of the {py:class}`~amplify.AcceptableDegrees` class to the {py:meth}`~amplify.Model.to_intermediate_model` method, you can also freely specify the type and degree of the variable to be converted.

```{testcode}
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
im, mapping = model.to_intermediate_model(bq)
```

In addition to specifying the variable type and degree, the {py:meth}`~amplify.Model.to_intermediate_model` method can specify variable conversion and degree reduction algorithms. The following explains the variable conversion and order reduction methods implemented in the Amplify SDK by looking at the {py:meth}`~amplify.Model.to_intermediate_model` method results.

## Variable conversion

The Amplify SDK converts a variable in an input model to another variable type. This conversion transforms the model into an intermediate model with variable types that the solver can handle.

Currently, the following variable conversions are implemented.

*   Conversion from integer to binary variables
*   Conversion from binary to Ising variables and vice versa

(encode-integer)=

### Conversion from integer to binary variables

For an integer variable $n$ with a lower limit of $l$ and an upper limit of $u$, several binary variables $q_0, q_1, ..., q_k$ are newly issued. Now, $n$ is converted to a polynomial:

$$
a_0 q_0 + a_1 q_1 + \cdots + a_k q_k + l.
$$

Here, the integer sequence $a_0, a_1, \ldots, a_k$ is determined so that the possible range of this polynomial matches the set of all integers between $l$ and $u$.

Four different algorithms are implemented to determine the number of variables $k$ and the sequence of coefficients $a_0, a_1, \ldots, a_k$ of the polynomial.

As an example, suppose the intermediate model is composed of binary variables for a model with the integer variable `n`{l=python} as the objective function that takes integers between -10 and 10 as follows. Let us see how the integer variable `n`{l=python} is transformed into a polynomial of binary variables in each algorithm.

```{testcode}
gen = VariableGenerator()
n = gen.scalar("Integer", bounds=(-10, 10)) # Issue an integer variable

model = Model(n)

bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
```

The conversion algorithm from integer variables to binary variables is specified in the `integer_encoding_method` keyword argument of the {py:meth}`~amplify.Model.to_intermediate_model` method and the {py:func}`~amplify.solve` function. The default is {py:class}`~amplify.IntegerEncodingMethod.Default`.

{py:class}`~amplify.IntegerEncodingMethod.Unary`
:   Sets the number of variables $k = u - l$, and $a_0 = a_1 = \cdots = a_k = 1$.

    ```{testcode}
    :hide:
    gen = VariableGenerator(); n = gen.scalar("Integer", bounds=(-10, 10)); model = Model(n)
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Unary")
    ```

    ```{doctest}
    >>> print(mapping[n])  # doctest: +NORMALIZE_WHITESPACE
    q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8 + q_9 + q_{10} + q_{11} + 
      q_{12} + q_{13} + q_{14} + q_{15} + q_{16} + q_{17} + q_{18} + q_{19} - 10
    ```

{py:class}`~amplify.IntegerEncodingMethod.Linear`
:   Assigns $(a_0, a_1, a_2, \ldots, a_{k-2}, a_{k-1}, a_k) = (1, 2, 3, \ldots, k-1, k, m)$.
    $k$ is the maximum integer satisfying $1 + 2 + 3 + \cdots + k \leq u - l$, and $m$ are the fraction.

    ```{testcode}
    :hide:
    gen = VariableGenerator(); n = gen.scalar("Integer", bounds=(-10, 10)); model = Model(n)
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Linear")
    ```

    ```{doctest}
    >>> print(mapping[n])
    q_0 + 2 q_1 + 3 q_2 + 4 q_3 + 5 q_4 + 5 q_5 - 10
    ```

{py:class}`~amplify.IntegerEncodingMethod.Binary`
:   Assigns $(a_0, a_1, a_2, a_3, \ldots, a_{k-1}, a_k) = (1, 2, 4, 8, \ldots, 2^{k-1}, m)$.
    $k$ is the maximum integer satisfying $1 + 2 + 4 + \cdots + 2^{k-1} \leq u - l$, and $m$ is the fraction.

    ```{testcode}
    :hide:
    gen = VariableGenerator(); n = gen.scalar("Integer", bounds=(-10, 10)); model = Model(n)
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Binary")
    ```

    ```{doctest}
    >>> print(mapping[n])
    q_0 + 2 q_1 + 4 q_2 + 8 q_3 + 5 q_4 - 10
    ```

{py:class}`~amplify.IntegerEncodingMethod.Default` (Default)
:   Of the above three algorithms, the one that uses the least number of variables $k$ is used.

```{note}
In {py:class}`~amplify.IntegerEncodingMethod.Linear` and {py:class}`~amplify.IntegerEncodingMethod.Binary`, if the fractions $m$, $m_1$, $m_2$ become $0$, the corresponding auxiliary variable is omitted from being issued.
```

### Conversion from Ising to binary variables

For an Ising variable $s$, issue a new binary variable $q$ to convert $s$ to $2 q -1$.

```{testcode}
gen = VariableGenerator()
s = gen.scalar("Ising")

model = Model(s)
bq = AcceptableDegrees(objective={"Binary": "Quadratic"})

im, mapping = model.to_intermediate_model(bq)
```

```{doctest}
>>> print(mapping[s])
2 q_0 - 1
```

### Conversion from binary to Ising variables

For a binary variable $q$, issue a new Ising variable $s$ to convert $q$ to $(s + 1) / 2$.

```{testcode}
gen = VariableGenerator()
q = gen.scalar("Binary")

model = Model(q)
iq = AcceptableDegrees(objective={"Ising": "Quadratic"})

im, mapping = model.to_intermediate_model(iq)
```

```{doctest}
>>> print(mapping[q])
0.5 s_0 + 0.5
```

## Degree reduction of binary variable polynomials

The Amplify SDK implements the ability to reduce the 3 or higher degree of a binary or Ising variable polynomial to a polynomial of degree 2 or higher. By applying variable conversion and degree reduction, the Amplify SDK converts third-order or higher polynomials involving integer variables to second-order polynomials with binary variables.

(quadratization-method)=

### Degree reduction algorithm

 Two algorithms are implemented: {py:class}`~amplify.QuadratizationMethod.IshikawaKZFD` and {py:class}`~amplify.QuadratizationMethod.Substitute`.

The degree reduction algorithm can be specified with the `quadratization_method` keyword argument of the {py:func}`~amplify.solve` function and the {py:meth}`~amplify.Model.to_intermediate_model` method. The default is {py:class}`~amplify.QuadratizationMethod.IshikawaKZFD`.

To see how the intermediate model is constructed as the degree is reduced in each algorithm, we create a model with the following third-order binary variable polynomial as the objective function. The intermediate model is also specified so that the objective function is binary quadratic and unconstrained.

```{testcode}
gen = VariableGenerator()
q = gen.array("Binary", 4)

model = Model(q[0] * q[2] * q[3] - q[1] * q[2] * q[3])

bq = AcceptableDegrees(objective={"Binary": "Quadratic"})
```

{py:class}`~amplify.QuadratizationMethod.IshikawaKZFD` (Default)
:   For each higher-order term of the polynomial, an auxiliary variable is issued and the degree of a higher-order term is reduced so that the value does not change when the auxiliary variable takes the optimal value.

   The following conversions are performed for third-order or higher terms with binary variables $k q_1 q_2 \cdots q_n$.

    *   If the coefficient $k$ of the term is negative, an auxiliary variable $x$ is issued and the term $k q_1 q_2 \cdots q_n$ is converted to:

        $$
        kx (q_1 + q_2 + \cdots + q_n + 1 - n).
        $$

    *   If the coefficient $k$ of the term is positive and the degree $n$ is even, issue $(n-2)/2$ number of auxiliary variables $x_1, x_2, \ldots, x_{\left(n-2 \right)/2}$ to convert the term $k q_1 q_2 \cdots q_n$ to:

        $$
        \begin{align*}
        & k \left(\frac{1}{2} S\left(S-1\right) - \sum_{i = 1}^{\frac{n-2}{2}}  x_i \left(2 \left(S - 2i\right) + 1\right) \right) \\
        & \text{where} \quad S = q_1 + q_2 + \cdots + q_n.
        \end{align*}
        $$

    *   If the coefficient of the term $k$ is positive and the degree $n$ is odd, $(n-1)/2$ number auxiliary variables $x_1, x_2, \ldots, x_{\left(n-1\right)/2}$ are issued to convert the term $k q_1 q_2 \cdots q_n$ to:

        $$
        \begin{align*}
        & k k \left(\frac{1}{2} S\left(S-1\right) - \sum_{i = 1}^{\frac{n-1}{2} - 1} x_i \left(2 \left(S - 2i\right) + 1\right) - x_{\frac{n-1}{2}} \left(S - n + 2\right) \right) \\
        & \text{where} \quad S = q_1 + q_2 + \cdots + q_n.
        \end{align*}
        $$

    ```{testcode}
    :hide:
    gen = VariableGenerator(); q = gen.array("Binary", 4); model = Model(q[0] * q[2] * q[3] - q[1] * q[2] * q[3])
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(
        bq, quadratization_method="IshikawaKZFD"
    )
    ```

    ```{doctest}
    >>> print(im) # doctest: +NORMALIZE_WHITESPACE
    minimize:
      q_0 q_2 + q_0 q_3 - q_0 q'_0 - q_1 q'_1 + q_2 q_3 
        - q_2 q'_0 - q_2 q'_1 - q_3 q'_0 - q_3 q'_1 + q'_0 + 2 q'_1
    ```

    Here, `q'_0` and `q'_1` are the auxiliary variables issued for each term.

    ```{attention}
    In the {py:class}`~amplify.QuadratizationMethod.IshikawaKZFD` algorithm, the degree of the constraints cannot be reduced. If you want to pass a constraint with a third-order constraint expression to a solver that accepts a second-order constraint expression, use the {py:class}`~amplify.QuadratizationMethod.Substitute` algorithm.
    ```

    ```{dropdown} For Ising variables

    The following conversions are performed for third-order or higher terms with Ising variables $k s_1 s_2 \cdots s_n$.

    *   If the coefficient of the term $k$ is positive and the degree $n$ is odd, or   
        coefficient $k$ is negative and the degree $n$ is even, then

        $\mathrm{floor} \left( n / 2 \right)$ number auxiliary variables $x_1, x_2, \ldots, x_{\mathrm{floor} \left( n / 2 \right)}$ are issued to convert the term $k s_1 s_2 \cdots s_n$ to:

        $$
        \begin{align*}
        & \left| k \right| \left( 2 S^2 - 8 \sum_{i = 1}^{\mathrm{floor} \left( n / 2 \right)}{ \left( \frac{x_i + 1}{2} \right) \left(  S - 2 i  + 1  \right) } - 1 \right) \\
        & \text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}}.
        \end{align*}
        $$

    *   If the coefficient of the term $k$ is positive and the degree $n$ is even, or   
        coefficient $k$ is negative and the degree $n$ is odd, then

        $\mathrm{floor} \left( \left(n-1\right) / 2 \right)$ number auxiliary variables $x_1, x_2, \ldots, x_{\mathrm{floor} \left( \left(n-1\right) / 2 \right)}$ are issued to convert the term $k s_1 s_2 \cdots s_n$ to:

        $$
        \begin{align*}
        & \left| k \right| \left( 2 \left(S-1\right)^2 - 8 \sum_{i = 1}^{\mathrm{floor} \left( \left(n-1\right) / 2 \right)}{ \left( \frac{x_i + 1}{2} \right) \left(  S - 2 i   \right) } - 1 \right) \\
        & \text{where} \quad S = \sum_{i =1}^{n}{\frac{s_i + 1}{2}}.
        \end{align*}
        $$
    ```

(substitution-multiplier)=

{py:class}`~amplify.QuadratizationMethod.Substitute`
:   For a product $q_a q_b$ of two binary variables that appears in a product of third order or higher, issue the auxiliary variable $x$ and replace all $q_a q_b$ in each term of the polynomial expression with $x$. The following constraints are then added to the intermediate model.

    $$
    \begin{align*}
    \text{subject to:} \quad & q_a q_b = x \\
    \text{penalty function:} \quad & q_a q_b - 2 q_a x - 2 q_b x + 3 x
    \end{align*}
    $$

    The above operations are repeated until the polynomial becomes second order.

    ```{testcode}
    :hide:
    gen = VariableGenerator(); q = gen.array("Binary", 4); model = Model(q[0] * q[2] * q[3] - q[1] * q[2] * q[3])
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(
        bq, quadratization_method="Substitute"
    )
    ```

    ```{doctest}
    >>> print(im)
    minimize:
      q_0 q'_0 - q_1 q'_0
    subject to:
      q_2 q_3 - q'_0 == 0 (weight: 2)
    ```

    In the above, we see that `q_0 q_1` has been replaced by the auxiliary variable `q'_0`.

    The weights of the penalty function for the constraints added by the order reduction are initially set to the sum of the absolute values of the coefficients of the terms in which the substitution occurs. This is because the weights must be large enough compared to the objective function. Since the initial values of the weights are sometimes too large, the `substitution_multiplier` keyword argument can be used to specify a coefficient for the initial values of the weights.

    ```{testcode}
    :hide:
    gen = VariableGenerator(); q = gen.array("Binary", 4); model = Model(q[0] * q[2] * q[3] - q[1] * q[2] * q[3])
    ```
    ```{testcode}
    im, mapping = model.to_intermediate_model(bq,
        quadratization_method="Substitute",
        substitution_multiplier=0.5
    )
    ```

    ```{doctest}
    >>> print(im)
    minimize:
      q_0 q'_0 - q_1 q'_0
    subject to:
      q_2 q_3 - q'_0 == 0 (weight: 1)
    ```

    ```{note}
    See "[](#penalty-weight)" for information on adjusting constraint weights.
    ```

````{tip}
Each degree reduction algorithm has the following characteristics. Depending on which algorithm is used, the number of variables in the intermediate model can vary greatly, which can affect the solver's feasibility and results.

```{list-table}
:width: 100%
:header-rows: 1
:stub-columns: 1
:widths: 1 2 2

* - Algorithm
  - Pros
  - Cons
* - {py:class}`~amplify.QuadratizationMethod.IshikawaKZFD`
  - The number of auxiliary variables is at most half the order of the higher order terms (one if the coefficient is negative).
  - The number of auxiliary variables is proportional to the number of higher order terms, so a large number of auxiliary variables may be needed.
* - {py:class}`~amplify.QuadratizationMethod.Substitute`
  - If substitution across terms works well, the number of auxiliary variables can be reduced.
  - Tuning may be needed for constraint penalty function weight adjustment
```
````

(intermediate-result)=

## Solver execution result and intermediate model

The result of the {py:func}`~amplify.solve` function execution can also provide information about the intermediate model and the result of solving for the intermediate model. You can obtain this information from the {py:attr}`~amplify.Result.intermediate` attribute of the {py:class}`~amplify.Result` class (the {py:class}`~amplify.Result.ModelConversion` class).

The {py:class}`~amplify.Result.ModelConversion` class has the following attributes.

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

* - Attribute
  - Data type
  - Details
* - {py:attr}`~amplify.Result.ModelConversion.model`
  - {py:class}`~amplify.Model`
  - Intermetiate model
* - {py:attr}`~amplify.Result.ModelConversion.mapping`
  - {py:class}`~amplify.Result.ModelConversion.IntermediateMapping`
  - Variable transformation map from input model variables to intermediate model variables
* - {py:attr}`~amplify.Result.ModelConversion.num_variables`
  - {py:class}`int`
  - Number of variables used in the intermediate model's objective function and constraints (including penalty functions, if generated)
* - {py:attr}`~amplify.Result.ModelConversion.values_list`
  - {py:class}`~amplify.Result.ValuesList`
  - Result of the intermediate model
```

As an example, let's execute {py:func}`~amplify.solve` with {py:class}`~amplify.FixstarsClient` for the following model with integer variables in the objective function.

```{testcode}
from amplify import VariableGenerator, Model, FixstarsClient, solve

gen = VariableGenerator()
n = gen.scalar("Integer", bounds=(1, 3)) # Issue an integer variable
model = Model(n)

client = FixstarsClient()
client.parameters.timeout = 1000

result = solve(model, client)
```

You can obtain information about the intermediate model from the {py:attr}`~amplify.Result.intermediate` attribute of the result.

```{doctest}
>>> print(result.intermediate.model)
minimize:
  q_0 + q_1 + 1
```

You can see how the integer variable `n`{l=python} is transformed in {py:attr}`~amplify.Result.ModelConversion.mapping` as follows.

```{doctest}
>>> print(result.intermediate.mapping[n])
q_0 + q_1 + 1
```

You can check the solution of the intermediate model with {py:attr}`~amplify.Result.ModelConversion.values_list`. {py:attr}`~amplify.Result.ModelConversion.values_list` can contain multiple solutions, so we obtain the first solution here.

```{doctest}
>>> result.intermediate.values_list[0]
Values({Poly(q_0): 0, Poly(q_1): 0})
```

The solution for the input model is obtained from the conversion of the solution of the intermediate model based on {py:attr}`~amplify.Result.ModelConversion.mapping`. Although a bit complicated, all intermediate model solutions can be transformed into input model solutions as follows.

```{doctest}
>>> im = result.intermediate
>>> {
...     var: im_mapped.evaluate(im_values)
...     for im_values in im.values_list
...     for var, im_mapped in im.mapping.items()
... }
{Poly(n_0): 1.0}
```

We can see that this is consistent with the {py:attr}`~amplify.Result.solutions` that are the output of {py:func}`~amplify.solve`.