Symbolic Math#

Note

This section currently describes symbolic math used for quadratic models such as the constrained quadratic model (CQM). For nonlinear models, see the Model Construction (Nonlinear Models) section.

The dimod package’s support for symbolic math can simplify your coding of problems. For example, consider a problem of finding the rectangle with the greatest area for a given perimeter, which you can formulate mathematically as,

\[ \begin{align}\begin{aligned}\textrm{Objective: } \quad &\max_{i,j} \quad ij\\\textrm{Constraint:} \quad &2i+2j \le 8\end{aligned}\end{align} \]

where the components are,

  • Variables: \(i\) and \(j\) are the lengths of two sides of the rectangle and the length of the perimeter is arbitrarily selected to be 8.

  • Objective: maximize the area, which is given by the standard geometric formula \(ij\).

  • Constraint: subject to not exceeding the given perimeter length; that is, \(2i+2j\), the summation of the rectangle’s four sides, is constrained to a maximum value of 8.

The dimod package’s symbolic math enables an intuitive coding of such problems:

>>> i, j = dimod.Integers(["i", "j"])
>>> objective = -i * j
>>> constraint = 2 * i + 2 * j <= 8
>>> print(objective.to_polystring())
-i*j
>>> print(constraint.to_polystring())
2*i + 2*j <= 8

Here variables i,j are of type integer, perhaps representing the number of tiles laid horizontally and vertically in creating a rectangular floor, and the coded objective is set to negative because D-Wave samplers minimize rather than maximize.

The foundation for this symbolic representation is single-variable models.

Variables as Models#

To symbolically represent an objective or constraint, you first need symbolic representations of variables.

Quadratic models with a single variable can represent your variables; for example, if the type of variable you need is integer:

>>> i = dimod.Integer('i')
>>> i
QuadraticModel({'i': 1.0}, {}, 0.0, {'i': 'INTEGER'}, dtype='float64')

Here, variable i is a QuadraticModel class that contains one variable with the label 'i'.

This works because quadratic models (QMs) have the form,

\[\sum_i a_i x_i + \sum_{i \le j} b_{i, j} x_i x_j + c\]

where \(\{ x_i\}_{i=1, \dots, N}\) can be integer variables (\(a_{i}, b_{ij}, c\) are real values). If you set \(a_1=1\) and all remaining coefficients to zero, the model represents a single variable, \(x_1\).

When your variable is used in a linear term of a polynomial, such as \(3.75i\), the coefficient (\(3.75\)) is represented in this same model by the value of the linear bias on the 'i'–labeled variable:

>>> 3.75 * i
QuadraticModel({'i': 3.75}, {}, 0.0, {'i': 'INTEGER'}, dtype='float64')

Similarly, when your variable is in a quadratic term, such as \(2.2i^2\), the coefficient (\(2.2\)) is represented in this same model by the value of the quadratic bias, \(b_{1, 1} = 2.2\):

>>> 3.75 * i + 2.2 * i * i
QuadraticModel({'i': 3.75}, {('i', 'i'): 2.2}, 0.0, {'i': 'INTEGER'}, dtype='float64')

You can see the various methods of creating such variables in the dimod package’s Generators reference documentation.

Typically, you have more than a single variable, and your variables interact.

Operations on Variables#

Consider a simple problem of a NOT operation between two binary variables. For \(\{-1, 1\}\)–valued binary variables, the NOT operation is equivalent to multiplication of the two variables:

>>> s1, s2 = dimod.Spins(["s1", "s2"])
>>> bqm_not = s1*s2
>>> bqm_not
BinaryQuadraticModel({'s1': 0.0, 's2': 0.0}, {('s2', 's1'): 1.0}, 0.0, 'SPIN')
>>> print(dimod.ExactSolver().sample(bqm_not))
  s1 s2 energy num_oc.
1 +1 -1   -1.0       1
3 -1 +1   -1.0       1
0 -1 -1    1.0       1
2 +1 +1    1.0       1
['SPIN', 4 rows, 4 samples, 2 variables]

The symbolic multiplication between variables above executes a multiplication between the models representing each variable. Binary quadratic models (BQM) are of the form:

\[\sum_{i=1} a_i v_i + \sum_{i<j} b_{i,j} v_i v_j + c \qquad\qquad v_i \in\{-1,+1\} \text{ or } \{0,1\}\]

where \(a_{i}, b_{ij}, c\) are real values. The multiplication of two such models, with linear terms \(a_1 = 1\), reduces to \(\sum_{i=1} 1 v_1 * \sum_{i=1} 1 u_1 = v_1 u_1\), a multiplication of two variables.

In this NOT example, because all the variables are the same Vartype class, the dimod package represents each binary variable, and their multiplication, with BinaryQuadraticModel objects.

>>> bqm_not.vartype is dimod.Vartype.SPIN
True

If an operation includes more than one type of variable, the representation is always a QuadraticModel class and the Vartype class is per variable:

>>> qm = bqm_not + 3.75 * i
>>> print(type(qm))
<class 'dimod.quadratic.quadratic_model.QuadraticModel'>
>>> qm.vartype("s1") == dimod.Vartype.SPIN
True
>>> qm.vartype("i") == dimod.Vartype.INTEGER
True

Note

An important distinction is that x = dimod.Binary('x'), for example, instantiates a model with a variable label 'x' and not a free-floating variable labeled x. Consequently, you can add x to another model by adding the two models,

>>> x = dimod.Binary("x")
>>> bqm = dimod.BinaryQuadraticModel('BINARY')
>>> bqm += x

which adds the variable labeled 'x' in the single-variable BQM, x, to model bqm. You cannot add x to a model—as though it were variable 'x'—by doing bqm.add_variable(x).

Representing Constraints#

Many real-world problems include constraints. Typically constraints are either equality or inequality, in the form of a left-hand side(lhs), right-hand side (rhs), and the dimod.sym.Sense (\(\le\), \(\ge\), or \(==\)). For example, the constraint of the rectangle problem above,

\[\textrm{s.t.} \quad 2i+2j \le P\]

has a lhs of \(2i+2j\) less or equal to a rhs of a some real number (\(8\)):

>>> print(constraint.lhs.to_polystring(), constraint.sense.value, constraint.rhs)  
2*i + 2*j <= 8

You can create such an equality or inequality symbolically, and it is shown with the model:

>>> print(type(3.75 * i <= 4))
<class 'dimod.sym.Le'>
>>> 3.75 * i <= 4
Le(QuadraticModel({'i': 3.75}, {}, 0.0, {'i': 'INTEGER'}, dtype='float64'), 4)

Note

The dimod package requires that the right-hand side of any equation to be a float or an int. For example,

\[i + j \le ij\]

can be transformed into a form supported by dimod by subtracting the right-hand side from both sides.

\[i + j - ij \le 0\]

You can then create the inequality symbolically.

i, j = dimod.Integers(['i', 'j'])
i + j - i*j <= 0

Performance#

The dimod package’s symbolic math is very useful for small models used for experimenting and formulating problems. It also offers some more performant functionality; for example, methods such as IntegerArray() for creating multiple variables with NumPy arrays or quicksum() as a replacement for the Python sum() function.

See the examples of BinaryArray(), IntegerArray(), and SpinArray() for usage.