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:

\[ a_0 q_0 + a_1 q_1 + \ldots + 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 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, m_1, m_2)\). \(k\) is the maximum integer satisfying \(1 + 2 + 3 + ... + (k - 1) \leq u - l\), and \(m_1\) and \(m_2\) are the fractions.

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 + ... + 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 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 convert a binary variable polynomial of degree 3 or higher to a binary variable polynomial of degree 2. By applying variable conversion and degree reduction, the Amplify SDK converts third-order or higher polynomials involving integer or Ising 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[1] * q[2] - q[0] * q[1] * q[3])

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

For each higher-order term of the polynomial, an auxiliary variable is issued and the higher-order term is converted to a quadratic polynomial so that the value does not change when the auxiliary variable takes the optimal value. Specifically, the following conversions are performed for third-order or higher terms \(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 order \(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 \biggl(\frac{1}{2} S(S-1) - \sum_{i = 1}^{\frac{n-2}{2}} x_i (2 (S - 2i) + 1) \biggr) \\ & \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 order \(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 \biggl(\frac{1}{2} S(S-1) - \sum_{i = 1}^{\frac{n-1}{2}} x_i (2 (S - 2i) + 1) + x_{\frac{n-1}{2}} (2 (S - n + 1) + 1)\biggr) \\ & \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_1 + q_0 q_2 - q_0 q'_0 - q_0 q'_1 + q_1 q_2 
    - q_1 q'_0 - q_1 q'_1 - q_2 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 below.

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_2 q'_0 - q_3 q'_0
subject to:
  q_0 q_1 - 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_2 q'_0 - q_3 q'_0
subject to:
  q_0 q_1 - 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().