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 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\) are newly issued. Now, \(n\) is converted to a polynomial:
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
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\).
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.
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
andq'_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 theSubstitute
algorithm.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{split} \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*} \end{split}\]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{split} \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*} \end{split}\]
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 variableq'_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 |
---|---|---|
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. |
|
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 |
---|---|---|
Intermetiate model |
||
Variable transformation map from input model variables to intermediate model variables |
||
Number of variables used in the intermediate model’s objective function and constraints (including penalty functions, if generated) |
||
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()
.