3. Polynomials and Objective Functions#

The objective function is a mathematical expression expressing the degree to which the objective in a combinatorial optimization problem is achieved; in the Amplify SDK, it is the polynomial you want to minimize. This page describes how to construct polynomials using the Amplify SDK.

Tip

Suppose you want to solve a combinatorial optimization problem where you want to maximize a polynomial. In that case, you can convert it to a minimization problem by multiplying its objective function by -1, allowing for optimization with the Amplify SDK.

3.1. Polynomial construction#

The Amplify SDK provides the polynomial class Poly to represent the objective function and constraint expressions for combinatorial optimization problems. Variables issued using the VariableGenerator class in the previous section are also instances of Poly.

You can easily create arbitrary polynomial expressions by performing quadrature operations and powers on variables created by VariableGenerator.

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", 6)
p = -q[0] + 2.3 * q[1] * q[2] - (q[3] + q[4]) ** 2 * q[5]

>>> print(p)
- 2 q_3 q_4 q_5 + 2.3 q_1 q_2 - q_3 q_5 - q_4 q_5 - q_0

Tip

The Amplify SDK also provides the logical operators defined below. These operators help create constraints from polynomials that are known to take only 0 or 1 values, such as a single binary variable.

Operator	Effect
`&` (logical AND)	`x & y` is equivalent to `x * y`.
`\|` (logical OR)	`x \| y` is equivalent to `-x * y + x + y`.
`^` (exclusive OR)	`x ^ y` is equivalent to `-2 * x * y + x + y`.

You can include variables from different variable arrays or of different types in the same polynomial if the same VariableGenerator created them.

gen = VariableGenerator()
q = gen.array("Binary", 3)
s = gen.array("Ising", 2)
n = gen.scalar("Integer", bounds=(-1, 2))
p = q[0] + s[1] - 2 * n

>>> print(p)
q_0 + s_1 - 2 n_0

Attention

You cannot combine variables issued from different VariableGenerator instances to create an objective function or constraint. A single formulation must use variables issued from the same VariableGenerator instance.

You can use the polynomial created as an objective function without modification. Thus, for example, if the objective function is \(q_0 q_1 - q_2\) then the objective function can be expressed as follows

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]

3.2. Constructing polynomials using polynomial arrays#

Note

This section is for users familiar with the NumPy library.

Using the array operations of the polynomial array class speeds up the polynomial generation and is intuitive for those familiar with the NumPy library. However, you can skip this section since you can already create arbitrary polynomials using the abovementioned methods.

The Amplify SDK provides the PolyArray class as a class representing an array of polynomials to make constructing polynomials easier and faster.

The PolyArray class is a NumPy-like multidimensional array that implements many methods compatible with NumPy’s ndarray array. The variable array created by the array() of the VariableGenerator class in the previous section is an instance of PolyArray.

The following example creates a 3x3 array of variables, just like a NumPy multidimensional array, with attributes representing the shape of the array and the number of dimensions, ndim.

from amplify import VariableGenerator

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

>>> q.shape
(3, 3)
>>> q.ndim
2

To retrieve an array element, specify the index as in the NumPy array.

>>> print(q[0, 0])
q_{0,0}

It is also possible to retrieve a subarray using a slice. A subarray return view, not copy.

>>> print(q[1:3, 0:2])
[[q_{1,0}, q_{1,1}],
 [q_{2,0}, q_{2,1}]]
>>> print(q[0, ::-1])
[q_{0,2}, q_{0,1}, q_{0,0}]
>>> print(q[..., 0])
[q_{0,0}, q_{1,0}, q_{2,0}]

sum() is one of the handy methods for creating polynomials from a polynomial array.

Calculating the sum of all variables:

>>> print(q.sum())
q_{0,0} + q_{0,1} + q_{0,2} + q_{1,0} + q_{1,1} + q_{1,2} + q_{2,0} + q_{2,1} + q_{2,2}

Calculating the sum row by row:

>>> print(q.sum(axis=1))  
[q_{0,0} + q_{0,1} + q_{0,2},
 q_{1,0} + q_{1,1} + q_{1,2},
 q_{2,0} + q_{2,1} + q_{2,2}]

Calculating the sum column by column:

>>> print(q.sum(axis=0))  
[q_{0,0} + q_{1,0} + q_{2,0},
 q_{0,1} + q_{1,1} + q_{2,1},
 q_{0,2} + q_{1,2} + q_{2,2}]

You can also perform quadrature operations on numbers and numpy arrays.

>>> print(2 * q)
[[2 q_{0,0}, 2 q_{0,1}, 2 q_{0,2}],
 [2 q_{1,0}, 2 q_{1,1}, 2 q_{1,2}],
 [2 q_{2,0}, 2 q_{2,1}, 2 q_{2,2}]]

>>> import numpy as np
>>> a = np.array([[1,2,3],[4,5,6],[7,8,9]])
>>> print(q * a)
[[  q_{0,0}, 2 q_{0,1}, 3 q_{0,2}],
 [4 q_{1,0}, 5 q_{1,1}, 6 q_{1,2}],
 [7 q_{2,0}, 8 q_{2,1}, 9 q_{2,2}]]

3.3. Properties and methods of polynomial#

This section introduces the methods and properties of the Poly class to get and change information about polynomials.

You can use the method degree() to get the degree of a polynomial. The methods is_number(), is_linear(), and is_quadratic() can tell if the polynomial is below a certain degree.

from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", 4)

>>> p = q[0] * q[1]
>>> p.degree()
2
>>> p.is_number()
False
>>> p.is_linear()
False
>>> p.is_quadratic()
True

The is_variable() method tests whether a polynomial can be considered a single variable, i.e., a one-dimensional monomial with coefficient 1. In particular, is_variable() returns True for scalar variables and elements of variable arrays created by the VariableGenerator.

>>> q[0].is_variable()
True
>>> (q[0] + 1).is_variable()
False
>>> (2 * q[0]).is_variable()
False

When is_variable() returns True, properties such as variable name name and type type are valid.

>>> q[0].name
'q_0'
>>> q[0].type
Binary