Nonlinear models typically represent general optimization problems with an objective function and/or one or more constraints over integer and/or binary variables; the model supports constraints natively.

This model is especially suited for use with decision variables that represent a common logic, such as subsets of choices or permutations of ordering. For example, in a traveling salesperson problem, permutations of the variables representing cities can signify the order of the route being optimized, and, in a knapsack problem, the variables representing items can be divided into subsets of packed and not packed. The design principles and major features of this solver are described in the dwave-optimization philosophy page.

Constrained quadratic models (CQM) are typically used for applications that optimize problems that might include binary-valued variables (both \(0/1\)-valued variables and \(-1/1\)-valued variables), integer-valued variables, and real variables (also known as continuous variables); the model supports constraints natively.

Binary quadratic models (BQM) are unconstrained and typically represent problems of decisions that could either be true (or yes) or false (no); for example, should an antenna transmit, or did a network node fail? The model uses \(0/1\)-valued variables and \(-1/1\)-valued variables; constraints are typically represented as penalty models.

Discrete quadratic models (DQM) are unconstrained and typically represent problems with several distinct options; for example, which shift should employee X work, or should the state on a map be colored red, blue, green, or yellow? The model uses variables that can represent a set of values such as {red, green, blue, yellow} or {3.2, 67}; constraints are typically represented as penalty models.

Ising models are unconstrained and typically represent problems of decisions that could either be true or or false. The model uses \(-1/1\)-valued variables; constraints are typically represented as penalty models.

The Ising model is traditionally used in statistical mechanics. In the formula below, \(N\) variables \(s=[s_1,...,s_N]\) correspond to physical Ising “spin up” (\(\uparrow\)) and “spin down” (\(\downarrow\)) states, which can represent \(+1\) and \(-1\) values in an objective function.

\[\text{E}(\vc s) = \sum_{i=1}^N h_i s_i + \sum_{i=1}^N \sum_{j=i+1}^N J_{i,j} s_i s_j \qquad\qquad s_i\in\{-1,+1\}\]

Here, the linear coefficients, \(h_i\), correspond to qubit biases, and relationships between the spins (interactions: correlations or anti-correlations), \(J_{i,j}\), correspond to coupling strengths.

QUBOs are unconstrained and typically represent problems of decisions that could either be true or false. The model uses \(0/1\)-valued variables; constraints are typically represented as penalty models.

QUBO problems are traditionally used in computer science. Variables take values \(1\) (TRUE) and \(0\) (FALSE).

A QUBO problem is defined using an upper-diagonal matrix \(Q\), which is an \(N \times N\) upper-triangular matrix of real weights, and \(x\), a vector of binary variables, as minimizing the function

\[f(x) = \sum_{i} {Q_{i,i}}{x_i} + \sum_{i<j} {Q_{i,j}}{x_i}{x_j}\]

where the diagonal terms \(Q_{i,i}\) are the linear coefficients and the nonzero off-diagonal terms \(Q_{i,j}\) are the quadratic coefficients.

This can be expressed more concisely as

\[\min_{{x} \in {\{0,1\}^n}} {x}^{T} {Q}{x}.\]

In scalar notation, the objective function expressed as a QUBO is as follows:

\[\text{E}_{qubo}(a_i, b_{i,j}; q_i) = \sum_{i} a_i q_i + \sum_{i<j} b_{i,j} q_i q_j.\]

Note

Quadratic unconstrained binary optimization problems—QUBOs—are unconstrained in that there are no constraints on the variables other than those expressed in Q.