Quadratic Model

This section describes the quadratic polynomial model (logical model) class and its peripheral functions.

Building Logical Model Objects

The objective function, represented by polynomials or matrices, and the constraints imposed on variables are abstracted as a “logical model” of a quadratic polynomial.

The correspondence between the input model class and the logical model class is as follows:

Logic model class

Input model class

BinaryQuadraticModel

BinaryPoly BinaryMatrix BinaryConstraint BinaryConstraints

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

BinaryIntQuadraticModel

BinaryIntPolyBinaryIntMatrix BinaryIntConstraint BinaryIntConstraints

IsingQuadraticModel

IsingPoly IsingMatrix

IsingIntPolyIsingIntMatrix

IsingIntQuadraticModel

IsingIntPoly IsingIntMatrix

The following can be given to construct logical model classes.

Note

For a concrete example of how to build a logical model, please see EXAMPLES, as it is closely related to the formulation of problems.

(Higher-order) Polynomial

Polynomial objects of binary or Ising variables can be converted to logical models. Higher-order polynomials greater than third-order can also be handled.

from amplify import BinaryPoly

f = BinaryPoly({(0, 1, 2): 2, (0, 1): 1, (0): 1, (1): 1, (2): 1}, -1)
model = BinaryQuadraticModel(f)

You can check the input model in the polynomial form with the input_poly property.

>>> f
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000

Matrix

A matrix object can be converted to a logical model.

from amplify import BinaryMatrix, BinaryQuadraticModel

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
model = BinaryQuadraticModel(m)

You can check the input model in the matrix form with the input_matrix property.

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)

Constraint

Single constraint condition

A constraint object can be converted to a logical model.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(c1)

You can check the constraints with the input_constraints property.

>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1)]

Multiple constraint conditions

Multiple constraint objects can be converted to a logical model.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(c1 + c2)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

Polynomials and Constraints

A logical model object can be constructed by imposing constraints on polynomials.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = BinaryQuadraticModel(f, c1 + c2)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

You can also generate a logical model object by adding constraints to a polynomial object. Please see “Constraint class addition operator” for details.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(sum_poly(q[:3]), 1)   # q_0 + q_1 + q_2 == 1
c2 = equal_to(sum_poly(q[1:]), 1)   # q_1 + q_2 + q_3 == 1
model = f + c1 + c2
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

Matrices and Constraints

from amplify import BinaryPoly, BinaryMatrix, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model = BinaryQuadraticModel(m, c1 + c2)
>>> model.input_matrix
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.0)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

A logical model object can be constructed by imposing constraints on matrices.

Operators of Logical Model Class

Adding a constraint object or constraint container to a logical model object will add a constraint. Please see “Constraint class addition operator” for details.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> len(model.input_constraints)
0
c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model += c1 + c2
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1), (q_1 + q_2 + q_3 == 1.000000, 1)]

Internals of Logical Model Class

The logical model class performs the conversion of the input model object to a quadratic polynomial, which can be handled by Ising machines, and it also handles the mapping between the indices of the input and logical variables.

In this section, we explain how to obtain the internal information of the logical models, which is the information of transformation and mapping from the input model.

Note

Basically, as long as the Solver class is used, there is no need to perform any post-construction operations on the logical model. The following is a description of internal information, and the interface may change in the future.

The following table lists the read-only properties that return the internal representation of the logical model class.

Input model

Logical expression

Logical model

Polynomial object

input_poly

logical_poly

logical_model_poly

Matrix object

input_matrix

logical_matrix

logical_model_matrix

Constraint objects

input_constraints

input_constraints/penalty

N/A

The input model is first converted into a logical expression. Logical expression is a term of convenience, referring to the expression obtained as the result of degree reduction from the input model to a quadratic polynomial and the corresponding index reassignment. The relation between input indices and logical indices is obtained as a dictionary with the logical_mapping property. In this dictionary, the keys are the input indices and the values are the logical indices.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 4)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
model = BinaryQuadraticModel(f)
>>> model.input_poly
2.000000 q_0 q_1 q_2 + q_0 q_1 + q_0 + q_1 + q_2 - 1.000000
>>> model.logical_poly
3.000000 q_0 q_1 + 2.000000 q_0 q_2 - 2.000000 q_0 q_3 + 2.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + q_0 + q_1 + q_2 + 2.000000 q_3 - 1.000000
>>> model.logical_mapping
{2: 2, 1: 0, 0: 1}

The logical model is then constructed by adding up the logical expressions and constraints.

c1 = equal_to(sum_poly(q[:3]), 1)
c2 = equal_to(sum_poly(q[1:]), 1)
model += c1 + c2
>>> model.logical_model_poly
5.000000 q_0 q_1 + 6.000000 q_0 q_2 - 2.000000 q_0 q_3 + 2.000000 q_0 q_4 + 4.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + 2.000000 q_2 q_4 - q_0 - q_2 + 2.000000 q_3 - q_4 + 1.000000

The above example shows how to obtain a polynomial from logical expressions and logical models, and it is also possible to obtain a matrix instead in the similar way.

Methods of the Logical Model Class

Obtaining the Number of Input Variables

The number of variables included in a input model can be obtained.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)

The number of variables that appear in the polynomial f will be returned.

>>> model.num_input_vars
3

Obtaining the Number of Logical Variables

The number of variables in a logical model can be obtained. More specifically, the number of variables in the quadratic polynomial, which is the internal representation of a logical model, is counted.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)

Please note that the number of logical variables does not necessarily match the number of variables in the input model. In the above example, the polynomial f is a higher-order polynomial, so it is transformed into a quadratic polynomial using auxiliary variables. Therefore, the number of variables in the logical model is the number of variables in the input model plus the number of auxiliary variables. You can check the polynomial expression of the logical model and the number of the logical variables as follows:

>>> model.logical_model_poly
2.000000 q_0 q_1 + 2.000000 q_0 q_2 - 2.000000 q_0 q_3 + 2.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + q_0 + q_1 + q_2 + 2.000000 q_3 - 1.000000
>>> model.num_logical_vars
4

Obtaining Constraint Objects

A container of constraint objects can be obtained.

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, sum_poly
from amplify.constraint import equal_to

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c = equal_to(sum_poly(q), 1)   # q_0 + q_1 + q_2 == 1
model = BinaryQuadraticModel(f, c)
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 1)]
>>> model.logical_model_poly
4.000000 q_0 q_1 + 4.000000 q_0 q_2 - 2.000000 q_0 q_3 + 4.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 + 2.000000 q_3

The strength coefficients of the constraints can be changed. After the change, the logical model is correspondingly altered.

>>> model.input_constraints[0][1] = 2
>>> model.input_constraints
[(q_0 + q_1 + q_2 == 1.000000, 2)]
>>> model.logical_model_poly
6.000000 q_0 q_1 + 6.000000 q_0 q_2 - 2.000000 q_0 q_3 + 6.000000 q_1 q_2 - 2.000000 q_1 q_3 - 2.000000 q_2 q_3 - q_0 - q_1 - q_2 + 2.000000 q_3 + 1.000000

Checking Constraint Satisfaction

check_constraints() checks if the constraint objects in the logical model satisfy all the imposed constraint condition at once. The form of its arguments is the same as is_satisfied(). See here for details.

This function is used to investigate which constraints are satisfied or not satisfied for a given solution. The strength coefficient values of the constraints in the logical model at that time can also be obtained and modified in the same way as Obtaining constraint objects.

from amplify import BinaryPoly, gen_symbols
from amplify.constraint import equal_to, less_equal

q = gen_symbols(BinaryPoly, 3)
f = 2 * q[0] * q[1] * q[2] + q[0] * q[1] + q[0] + q[1] + q[2] - 1
c1 = equal_to(q[0] + q[2], 1)  # q_0 + q_2 == 1
c2 = less_equal(q[0] + q[1], 1)  # q_0 + q_1 <= 1
model = f + c1 + c2
checked = model.check_constraints([1, 1, 0])  # q[0] = q[1] = 1, q[2] = 0
>>> checked
[((q_0 + q_2 == 1.000000, 1), True),
 ((q_0 + q_1 <= 1, 1), False)]

The output is returned as a container of the pairs of constraint object and result of the constraint check. In the above, we check if q = [1, 1, 0] satisfies the constraint, and the result means that q_0 + q_2 == 1 is satisfied, but q_0 + q_1 <= 1 is not.

This allows us to, for example, change the strength coefficient value for a constraint object if the constraint is not satisfied.

for c in checked:
    if c[1] is False:
        c[0][1] *= 2
>>> model.input_constraints
[(q_0 + q_2 == 1.000000, 1),
 (q_0 + q_1 <= 1, 2)]