# 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. ``` ```{seealso} 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 {math}`Q` and a vector of real numbers {math}`p` such that {math}`x^\top Q x + p^\top x + c` is represented. See [](matrix.md) for details. ``` (polynomial)= ## Polynomial construction The Amplify SDK provides the polynomial class {py:class}`~amplify.Poly` to represent the objective function and constraint expressions for combinatorial optimization problems. Variables issued using the {py:class}`~amplify.VariableGenerator` class in the previous section are also instances of {py:class}`~amplify.Poly`. You can easily create arbitrary polynomial expressions by performing quadrature operations and powers on variables created by {py:class}`~amplify.VariableGenerator`. ```{testcode} 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] ``` ```{doctest} >>> 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. ```{list-table} :header-rows: 1 * - Operator - Effect * - `&`{l=python} (logical AND) - `x & y`{l=python} is equivalent to `x * y`{l=python}. * - `|`{l=python} (logical OR) - `x | y`{l=python} is equivalent to `-x * y + x + y`{l=python}. * - `^`{l=python} (exclusive OR) - `x ^ y`{l=python} is equivalent to `-2 * x * y + x + y`{l=python}. ``` ```` You can include variables from different variable arrays or of different types in the same polynomial if the same {py:class}`~amplify.VariableGenerator` created them. ```{testcode} 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 ``` ```{doctest} >>> print(p) q_0 + s_1 - 2 n_0 ``` ```{attention} You cannot combine variables issued from different {py:class}`~amplify.VariableGenerator` instances to create an objective function or constraint. A single formulation must use variables issued from the same {py:class}`~amplify.VariableGenerator` instance. ``` You can use the polynomial created as an objective function without modification. Thus, for example, if the objective function is {math}`q_0 q_1 - q_2` then the objective function can be expressed as follows ```{testcode} gen = VariableGenerator() q = gen.array("Binary", 3) objective = q[0] * q[1] - q[2] ``` (poly-array)= ## 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 {py:class}`~amplify.PolyArray` class as a class representing an array of polynomials to make constructing polynomials easier and faster. The {py:class}`~amplify.PolyArray` class is a NumPy-like multidimensional array that implements many methods compatible with NumPy's {py:class}`~numpy.ndarray` array. The variable array created by the {py:meth}`~amplify.VariableGenerator.array` of the {py:class}`~amplify.VariableGenerator` class in the previous section is an instance of {py:class}`~amplify.PolyArray`. The following example creates a 3x3 array of variables, just like a NumPy multidimensional array, with attributes representing the {py:attr}`~amplify.PolyArray.shape` of the array and the number of dimensions, {py:attr}`~amplify.PolyArray.ndim`. ```{testcode} from amplify import VariableGenerator gen = VariableGenerator() q = gen.array("Binary", shape=(3, 3)) ``` ```{doctest} >>> q.shape (3, 3) >>> q.ndim 2 ``` To retrieve an array element, specify the index as in the NumPy array. ```{doctest} >>> print(q[0, 0]) q_{0,0} ``` It is also possible to retrieve a subarray using a slice. A subarray return view, not copy. ```{doctest} >>> 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}] ``` {py:meth}`~amplify.PolyArray.sum` is one of the handy methods for creating polynomials from a polynomial array. * Calculating the sum of all variables: ```{doctest} >>> 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: ```{doctest} >>> print(q.sum(axis=1)) # doctest: +NORMALIZE_WHITESPACE [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: ```{doctest} >>> print(q.sum(axis=0)) # doctest: +NORMALIZE_WHITESPACE [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. ```{doctest} >>> 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}]] ``` ```{doctest} >>> 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}]] ``` ```{seealso} In addition to the above, the {py:class}`~amplify.PolyArray` class provides various functions and methods such as broadcast, matrix product, and {py:func}`~amplify.einsum` functions. For a complete list of functions, see the {py:class}`~amplify.PolyArray` class reference. For the effects of NumPy-compatible methods, see {py:class}`numpy.ndarray`. ``` ## Properties and methods of polynomial This section introduces the methods and properties of the {py:class}`~amplify.Poly` class to get and change information about polynomials. You can use the method {py:meth}`~amplify.Poly.degree` to get the degree of a polynomial. The methods {py:meth}`~amplify.Poly.is_number`, {py:meth}`~amplify.Poly.is_linear`, and {py:meth}`~amplify.Poly.is_quadratic` can tell if the polynomial is below a certain degree. ```{testcode} from amplify import VariableGenerator gen = VariableGenerator() q = gen.array("Binary", 4) ``` ```{doctest} >>> p = q[0] * q[1] >>> p.degree() 2 >>> p.is_number() False >>> p.is_linear() False >>> p.is_quadratic() True ``` The {py:meth}`~amplify.Poly.is_variable` method tests whether a polynomial can be considered a single variable, i.e., a one-dimensional monomial with coefficient 1. In particular, {py:meth}`~amplify.Poly.is_variable` returns {py:obj}`True` for scalar variables and elements of variable arrays created by the {py:class}`~amplify.VariableGenerator`. ```{doctest} >>> q[0].is_variable() True >>> (q[0] + 1).is_variable() False >>> (2 * q[0]).is_variable() False ``` When {py:meth}`~amplify.Poly.is_variable` returns {py:obj}`True`, properties such as variable name {py:attr}`~amplify.Poly.name` and type {py:attr}`~amplify.Poly.type` are valid. ```{doctest} >>> q[0].name 'q_0' >>> print(q[0].type) Binary ``` ```{seealso} See "[](#variable-info)" for detailed information about variables in polynomials, such as {py:attr}`~amplify.Poly.name` and {py:attr}`~amplify.Poly.type`. ``` You can obtain information about all variables in the polynomial from the {py:attr}`~amplify.Poly.variables` property. ```{doctest} >>> (q[0] + 2 * q[1]).variables # doctest: +NORMALIZE_WHITESPACE [Variable({name: q_0, id: 0, type: Binary}), Variable({name: q_1, id: 1, type: Binary})] ``` The {py:meth}`~amplify.Poly.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 {py:class}`~amplify.Poly` class. The key of the argument must be a {py:class}`~amplify.Poly` that can be considered a variable, and the value must be a {py:class}`float` or a {py:class}`~amplify.Poly`. ```{doctest} >>> p = q[0] + q[1] >>> print((q[0] + q[1]).substitute({q[0]: 1, q[1]: 0})) 1 >>> print((q[0] + q[1]).substitute({q[0]: 1})) q_1 + 1 >>> print((q[0] + q[1]).substitute({q[1]: q[2] * q[3]})) q_2 q_3 + q_0 ``` ````{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 {py:class}`~amplify.PolyArray`. ```{doctest} >>> 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] ``` ````