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.

See also

Another way to implement the objective function is using a multidimensional polynomial coefficient array. This method is useful when the objective function has already been computed as a 2-dimensional array of real numbers \(Q\) and a vector of real numbers \(p\) such that \(x^\top Q x + p^\top x + c\) is represented. See Objective Function with a Coefficient Matrix for details.

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}]]

See also

In addition to the above, the PolyArray class provides various functions and methods such as broadcast, matrix product, and einsum() functions. For a complete list of functions, see the PolyArray class reference. For the effects of NumPy-compatible methods, see numpy.ndarray.

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'
>>> print(q[0].type)
Binary

See also

See “Getting variable information” for detailed information about variables in polynomials, such as name and type.

You can obtain information about all variables in the polynomial from the variables property.

>>> (q[0] + 2 * q[1]).variables 
[Variable({name: q_0, id: 0, type: Binary}),
 Variable({name: q_1, id: 1, type: Binary})]

The substitute() method obtains the result of assigning numbers or other polynomials to variables of a polynomial expression. This method takes a dict argument and returns an instance of the Poly class. The key of the argument must be a Poly that can be considered a variable or Variable, and the value must be a float or a Poly.

>>> p = q[0] + q[1]
>>> print(p.substitute({q[0]: 1, q[1]: 0}))
1
>>> print(p.substitute({q[0]: 1}))
q_1 + 1
>>> print(p.substitute({q[1]: q[2] * q[3]}))
q_2 q_3 + q_0
>>> v = p.variables
>>> print(p.substitute({v[0]: 1, v[1]: 0}))
1

Tip

If you want to perform a batch assignment for all polynomials in a polynomial array, you can use the ~amplify.PolyArray.substitute method of PolyArray.

>>> print(q)
[q_0, q_1, q_2, q_3]
>>> print(q.substitute({q[0]: 1, q[1]: 0}))
[  1,   0, q_2, q_3]
>>> print(q.substitute({q[1]: q[2] * q[3]}))
[    q_0, q_2 q_3,     q_2,     q_3]