Constrained Quadratic Models

The constrained quadratic model (CQM) are problems of the form:

\[\begin{split}\begin{align} \text{Minimize an objective:} & \\ & \sum_{i} a_i x_i + \sum_{i \le j} b_{ij} x_i x_j + c, \\ \text{Subject to constraints:} & \\ & \sum_i a_i^{(m)} x_i + \sum_{i \le j} b_{ij}^{(m)} x_i x_j+ c^{(m)} \circ 0, \quad m=1, \dots, M, \end{align}\end{split}\]

where \(\{ x_i\}_{i=1, \dots, N}\) can be binary[1], integer, or continuous[2] variables, \(a_{i}, b_{ij}, c\) are real values, \(\circ \in \{ \ge, \le, = \}\) and \(M\) is the total number of constraints.

[1]

For binary variables, the range of the quadratic-term summation is \(i < j\) because \(x^2 = x\) for binary values \(\{0, 1\}\) and \(s^2 = 1\) for spin values \(\{-1, 1\}\).

[2]

Real-valued variables are currently not supported in quadratic interactions.

The dimod.ConstrainedQuadraticModel class can contain this model and its methods provide convenient utilities for working with representations of a problem.