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