Models

To express your problem as an objective function and submit to a D-Wave sampler for solution, you formulate a model.

Constrained Versus Unconstrained

Many real-world problems include constraints. For example, a routing problem might limit the number of airplanes on the ground at an airport and a scheduling problem might require a minimum interval between shifts.

Constrained models such as the ConstrainedQuadraticModel model can support constraints by encoding both an objective and its set of constraints, as models or in symbolic form.

Unconstrained quadratic models are used to submit problems to samplers such as D-Wave quantum computers[1] and some quantum-classical hybrid samplers[2]. When using such samplers to handle problems with constraints, you typically formulate the constraints as penalty models.

The Supported Models section below lists constrained and unconstrained models.

[1]

D-Wave quantum computers accept unconstrained binary quadratic models, such as quadratic unconstrained binary optimization (QUBO) models: binary because variables are represented by qubits that return two states and quadratic because polynomial terms of two variables can be represented by pairs of coupled qubits.

[2]

Some hybrid samplers accept constrained and non-binary models; for example, a quadratic model with an integer variable that must be smaller than some configured value. See the Solver Properties & Parameters section For the available hybrid solvers and their capabilities.

Supported Models

The following table shows the models currently supported by Ocean software, the variables you can use with each, and some related classes.

Table 101 Supported Models

Model	Variables	Ocean Class & Sampler
Constrained:
Nonlinear Model	Binary, integer	Model, LeapHybridNLSampler
Constrained Quadratic Model	Binary, integer, real	ConstrainedQuadraticModel, LeapHybridCQMSampler
Unconstrained:
Ising Model	Spin	BinaryQuadraticModel, DWaveSampler
QUBO	Binary	BinaryQuadraticModel, DWaveSampler
Binary Quadratic Models	Binary, spin	BinaryQuadraticModel, LeapHybridSampler, DWaveSampler
Discrete Quadratic Models	Binary, discrete	DiscreteQuadraticModel, LeapHybridDQMSampler

Nonlinear Model

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.

For an introduction to Ocean software’s nonlinear model, see the Model Construction (Nonlinear Models) section.

Constrained Quadratic Model

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.

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[3], integer, or continuous[4] variables, \(a_{i}, b_{ij}, c\) are real values, \(\circ \in \{ \ge, \le, = \}\) and \(M\) is the total number of constraints.

[3]

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\}\).

[4]

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

For constructing quadratic models in Ocean software, see the Model Construction (Quadratic Models) section.

Binary Quadratic Models

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.

The binary quadratic model (BQM) class encodes Ising and quadratic unconstrained binary optimization (QUBO) models used by samplers such as the D-Wave quantum computer.

The BQM equation,

\[E(\bf{v}) = \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\}\]

can represent both.

Ising Model

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.

QUBO

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.

Other Models

Ocean software also supports these additional models.

Quadratic Models

Quadratic models are polynomials with one or two variables per term. A simple example of a quadratic model is,

\[Ax + By + Cxy\]

where \(A\), \(B\), and \(C\) are constants. Single-variable terms—\(Ax\) and \(By\) here—are linear with the constant biasing the term’s variable. Two-variable terms—\(Cxy\) here—are quadratic with a relationship between the variables.

Quantum computers solve hard problems by minimizing an objective function. Quadratic models are useful objective functions because the quantum processing unit (QPU) can represent binary variables as the states of the qubits and linear and quadratic coefficients as, respectively, the physical biases and couplings applied to these qubits. Hybrid quantum-classical samplers, which minimize some parts of the objective function using classical heuristics and some by using the QPU, enable the further abstraction of problem representation.

Ocean supports various quadratic models:

• Ising Model and QUBO

• Binary Quadratic Models are unconstrained and support binary variables.

• Constrained Quadratic Model can be constrained and support real, integer and binary variables.

• Discrete Quadratic Models are unconstrained and support discrete variables.

Ocean also provides support for higher order models, which are typically reduced to quadratic for sampling.

Discrete Quadratic Models

The discrete quadratic model (DQM) is a polynomial over discrete variables, with all terms of degree two or less, where a discrete variable represents some collection of distinct values, such as {red, green, blue, yellow} or {3.2, 67}, which are called the variable’s cases.

A discrete quadratic model may be defined as

\[H(\bf{d}) = \sum_{i} a_i(\bf{d}_i) + \sum_{i,j} b_{i,j}(\bf{d}_i,\bf{d}_j) + c\]

where \(\bf{d}_i\) are the discrete variables, \(a_i()\) and \(b_{i,j}()\) are real-valued functions, and \(c\) is a constant (offset).

You can represent any DQM with an equivalent model over binary variables by replacing each discrete variable, \(\bf{d}_i\), with a vector of binary variables using one-hot encoding, where exactly one binary variable is True and all others are False: \(\sum_a x_{i,a} = 1 \quad \forall i\).

In particular, a discrete quadratic model for \(N\) discrete variables, \(\bf{d}_i\), each with \(n_i\) cases, is then defined by using a binary variable, \(x_{i,u}\), to indicate whether discrete variable \(\bf{d}_i\) is set to case \(u\). The objective function can be expressed by the equation:

\[E(\bf{x}) = \sum_{i=1}^N \sum_{u=1}^{n_i} a_{i,u} x_{i,u} + \sum_{i=1}^N \sum_{j=i+1}^N \sum_{u=1}^{n_i} \sum_{v=1}^{n_j} b_{i,j,u,v} x_{i,u} x_{j,v} + c\]

Both representations are equivalent over the feasible space; that is, the solutions that meet the one-hot-encoding constraints. The second representation ascribes energies both to the feasible space (satisfying constraints), and an infeasible space (violating constraints). The second representation is used by Ocean tools.

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

Related Information

• Model Construction (Nonlinear Models) describes the construction of nonlinear models.

• Model Construction (Quadratic Models) describes the construction of quadratic models.