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 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 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 to_intermediate_model() method; use it to see how Amplify SDK performs variable transformations and order reduction within the solve() function.

You can specify the intermediate model’s variable type and polynomial degree in the first argument of the to_intermediate_model() method. If you want to use the degree that the solver can handle, pass the acceptable_degrees property as follows.

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 to_intermediate_model() method returns an intermediate model and a map of variable conversions from the input model to the intermediate model.

For example, FixstarsClient can handle a quadratic polynomial of binary variables as an objective function, as seen in “Intermediate model construction.” In the above example, the input model is a cubic polynomial of binary variables, but the to_intermediate_model() method converts the intermediate model’s objective function to a quadratic polynomial of binary variables.

>>> 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 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 AcceptableDegrees class to the to_intermediate_model() method, you can also freely specify the type and degree of the variable to be converted.

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

In addition to specifying the variable type and degree, the 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 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 real to binary variables
Conversion from binary to Ising variables and vice versa

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-1}\) are newly issued. Now, \(n\) is converted to a polynomial:

\[ a_0 q_0 + a_1 q_1 + \cdots + a_{k-1} q_{k-1} + l. \]

Here, the integer sequence \(a_0, a_1, \ldots, a_{k-1}\) 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-1}\) of the polynomial.

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

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 to_intermediate_model() method and the solve() function. The default is Default.

Unary

Sets the number of variables \(k = u - l\), and \(a_0 = a_1 = \cdots = a_{k-1} = 1\).

im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Unary")

>>> print(mapping[n])  
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

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.

im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Linear")

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

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.

im, mapping = model.to_intermediate_model(bq, integer_encoding_method="Binary")

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

Default (Default)

Of the above three algorithms, the one that uses the least number of variables \(k\) is used.

Note

In Linear and Binary, if the fractions \(m\), \(m_1\), \(m_2\) become \(0\), the corresponding auxiliary variable is omitted from being issued.

Conversion from real to binary variables¶

For a real variable \(x\) with a lower limit of \(l\) and an upper limit of \(u\), newly create several binary variables \(q_0, q_1, ..., q_{k-1}\). Then, \(x\) is converted to a polynomial:

\[ a_0 q_0 + a_1 q_1 + \cdots + a_{k-1} q_{k-1} + l, \]

where the coefficients \(a_0, a_1, \ldots, a_{k-1}\) are positive real numbers satisfying \(a_0 + a_1 + \cdots a_{k-1} = u - l\).

Several algorithms are implemented to determine the coefficients of the polynomial \(a_0, a_1, \ldots, a_{k-1}\).

For example, the model with the real variable x as the objective function taking reals between -10 and 10 is converted into a polynomial of binary variables as follows. Let us see how the real variable x is transformed into a polynomial of binary variables in each algorithm.

gen = VariableGenerator()
x = gen.scalar("Real", bounds=(-10, 10))

model = Model(x)

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

The conversion algorithm from real variables to binary variables is specified in the real_encoding_method keyword argument of the to_intermediate_model() method and the solve() function. The default is Random16.

Random

Set \((a_0, a_1, a_2, a_3, \ldots, a_{k-1})\) by uniform random numbers. The number of binary variables \(k\) is one of (4, 8, 16, 32), which is extracted from the last digits of the conversion algorithm name. The following is an example for \(k = 16\).

amplify.set_seed(0)
im, mapping = model.to_intermediate_model(bq, real_encoding_method="Random16")

>>> print(mapping[x])
1.99333941505556 q_0 + 1.05184485013684 q_1 + 1.18505654902564 q_2 + 1.49764241671521 q_3 + 1.76252706549575 q_4 + 0.841695701394766 q_5 + 0.21960146400976 q_6 + 0.635503335788004 q_7 + 1.80253453941945 q_8 + 0.173438994097798 q_9 + 2.04763527252344 q_{10} + 0.611762636976138 q_{11} + 1.95487069012893 q_{12} + 1.62228108547751 q_{13} + 1.9691590736731 q_{14} + 0.631106910082103 q_{15} - 10

Note

You can set the seed of random numbers used for variable conversion with the set_seed() function.

Note

In Poly, terms with coefficients less than 1e-10 are ignored to deal with numerical errors in symbolic processing.
Therefore, some of the terms of the transformed binary variable may be lost when the difference between the upper and lower limits \(u - l\) is very small.

Conversion from Ising to binary variables¶

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

gen = VariableGenerator()
s = gen.scalar("Ising")

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

im, mapping = model.to_intermediate_model(bq)

>>> 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\).

gen = VariableGenerator()
q = gen.scalar("Binary")

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

im, mapping = model.to_intermediate_model(iq)

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

Degree reduction algorithm¶

Two algorithms are implemented: IshikawaKZFD and Substitute.

The degree reduction algorithm can be specified with the quadratization_method keyword argument of the solve() function and the to_intermediate_model() method. The default is 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.

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"})

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{split} \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*} \end{split}\]
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{split} \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*} \end{split}\]

im, mapping = model.to_intermediate_model(
    bq, quadratization_method="IshikawaKZFD"
)

>>> print(im) 
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 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 Substitute algorithm.

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{split} \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*} \end{split}\]

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

im, mapping = model.to_intermediate_model(
    bq, quadratization_method="Substitute"
)

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

im, mapping = model.to_intermediate_model(bq,
    quadratization_method="Substitute",
    substitution_multiplier=0.5
)

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

Algorithm	Pros	Cons
`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.
`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

Solver execution result and intermediate model¶

The result of the 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 intermediate attribute of the Result class (the ModelConversion class).

The ModelConversion class has the following attributes.

Attribute	Data type	Details
`model`	`Model`	Intermetiate model
`mapping`	`IntermediateMapping`	Variable transformation map from input model variables to intermediate model variables
`num_variables`	`int`	Number of variables used in the intermediate model’s objective function and constraints (including penalty functions, if generated)
`values_list`	`ValuesList`	Result of the intermediate model

As an example, let’s execute solve() with FixstarsClient for the following model with integer variables in the objective function.

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 intermediate attribute of the result.

>>> print(result.intermediate.model)
minimize:
  q_0 + q_1 + 1

You can see how the integer variable n is transformed in mapping as follows.

>>> print(result.intermediate.mapping[n])
q_0 + q_1 + 1

You can check the solution of the intermediate model with values_list. values_list can contain multiple solutions, so we obtain the first solution here.

>>> 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 mapping. Although a bit complicated, all intermediate model solutions can be transformed into input model solutions as follows.

>>> 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 solutions that are the output of solve().