Quadratic Models: Unconstrained¶
This page describes the dimod package’s unconstrained quadratic models: classes, attributes, methods, and some functions related to these classes. For an introduction and the data structure, see Quadratic Models: Unconstrained.
For reference documentation of constrained quadratic models, see Quadratic Models: Constrained.
Quadratic Models¶
For an introduction to QMs, see Concepts: Quadratic Models.
QM Class¶
- class QuadraticModel(linear: Optional[Mapping[Hashable, Union[float, numpy.floating, numpy.integer]]] = None, quadratic: Optional[Mapping[Tuple[Hashable, Hashable], Union[float, numpy.floating, numpy.integer]]] = None, offset: Union[float, numpy.floating, numpy.integer] = 0, vartypes: Optional[Union[Mapping[Hashable, dimod.vartypes.Vartype], Iterable[Tuple[Hashable, Union[dimod.vartypes.Vartype, str, frozenset]]]]] = None, *, dtype: Union[numpy.dtype, None, type, numpy.typing._dtype_like._SupportsDType[numpy.dtype], str, Tuple[Any, int], Tuple[Any, Union[typing_extensions.SupportsIndex, Sequence[typing_extensions.SupportsIndex]]], List[Any], numpy.typing._dtype_like._DTypeDict, Tuple[Any, Any]] = None)[source]¶
A quadratic model.
Quadratic models are problems of the form:
\[E(x) = \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 binary1 or integer variables and \(a_{i}, b_{ij}, c\) are real values.
- 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\}\).
Attributes¶
Adjacency structure as a nested mapping of mappings. |
|
Data-type of the model's biases. |
|
Linear biases as a mapping. |
|
Number of interactions in the model. |
|
Number of variables in the model. |
|
Constant energy offset associated with the model. |
|
Quadratic biases as a flat mapping. |
|
A 2-tuple of |
|
The variables of the quadratic model. |
Methods¶
|
Add a linear bias to an existing variable or a new variable with specified vartype. |
|
Add variables and linear biases to a quadratic model. |
|
Add quadratic bias to a pair of variables. |
|
Add quadratic biases. |
|
Add a variable to the quadratic model. |
|
Add multiple variables of the same type to the quadratic model. |
|
Add variables from another model. |
|
Change the variable type of the given variable, updating the biases. |
|
Return a copy. |
|
Return the degree of specified variable. |
|
Determine the energies of the given samples-like. |
|
Determine the energy of the given sample. |
|
Remove a variable by fixing its value. |
|
Fix the value of the variables and remove them. |
Flip the specified binary-valued variable. |
|
|
Construct a quadratic model from a binary quadratic model. |
|
Construct a quadratic model from a file-like object. |
|
Get the linear bias of the specified variable. |
|
Get the quadratic bias of the specified pair of variables. |
|
Test for near equality to all biases of a given quadratic model. |
|
Return True if the given model has the same variables, vartypes and biases. |
Return True if the model has no quadratic interactions. |
|
Iterate over the variables and their biases. |
|
Iterate over the neighbors and quadratic biases of a variable. |
|
Iterate over the interactions of a quadratic model. |
|
|
Return the lower bound on the specified variable. |
|
Get the total bytes consumed by the biases, vartype info, bounds, and indices. |
|
Set the lower bound for a variable. |
|
Set the upper bound for a variable. |
|
Apply function of two arguments cumulatively to the linear biases. |
|
Apply function of two arguments cumulatively to the quadratic biases associated with a single variable. |
|
Apply function of two arguments cumulatively to the quadratic biases. |
|
Relabel the variables according to the given mapping. |
|
Relabel the variables as [0, n) and return the mapping. |
|
Remove the interaction between u and v. |
|
Remove the specified variable from the quadratic model. |
|
Scale the biases by the given number. |
|
Set the linear bias of a variable in the quadratic model. |
|
Set the quadratic bias between a pair of variables in the quadratic model. |
|
Convert any spin-valued variables to binary-valued. |
|
Serialize the QM to a file-like object. |
|
Return a string representing the model as a polynomial. |
|
Update the quadratic model from another quadratic model. |
|
Return the upper bound on the specified variable. |
|
The variable type of the given variable. |
Binary Quadratic Models¶
For an introduction to BQMs, see Concepts: Binary Quadratic Models.
BQM Class¶
- class BinaryQuadraticModel(*args, offset: Optional[Union[float, numpy.floating, numpy.integer]] = None, vartype: Optional[Union[dimod.vartypes.Vartype, str, frozenset]] = None, dtype: Union[numpy.dtype, None, type, numpy.typing._dtype_like._SupportsDType[numpy.dtype], str, Tuple[Any, int], Tuple[Any, Union[typing_extensions.SupportsIndex, Sequence[typing_extensions.SupportsIndex]]], List[Any], numpy.typing._dtype_like._DTypeDict, Tuple[Any, Any]] = None)[source]¶
Binary quadratic model.
Binary quadratic models (BQMs) are problems of the form:
\[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\}\]where \(a_{i}, b_{ij}, c\) are real values.
This class encodes Ising and quadratic unconstrained binary optimization (QUBO) models used by samplers such as the D-Wave system.
With one or more of the following parameters,
vartype
: The valid variable types for binary quadratic models, is one of:bqm
: An existing BQM.n
: Required number of variables.quadratic
: Quadratic biases, as a dictionary of form{(u, v): b, ...}
or a square array_like.linear
: Linear biases, as a dictionary of the form{v: b, ...}
or a one-dimensional array_like.offset
: Offset as a number.
you can create BQMs in several ways:
BinaryQuadraticModel(vartype)
with no variables or interactions.BinaryQuadraticModel(bqm)
from an existing BQM. The resulting BQM has the same variables, linear biases, quadratic biases and offset asbqm
.BinaryQuadraticModel(bqm, vartype)
from an existing BQM, changing to the specifiedvartype
if necessary.BinaryQuadraticModel(n, vartype)
withn
variables, indexed linearly from zero, setting all biases to zero.BinaryQuadraticModel(quadratic, vartype)
from quadratic biases. When formed with SPIN-variables, biases on the diagonal are added to the offset.BinaryQuadraticModel(linear, quadratic, vartype)
from linear and quadratic biases.BinaryQuadraticModel(linear, quadratic, offset, vartype)
from linear and quadratic biases and an offset.
- Parameters
*args – See above.
offset – Offset (see above) may be supplied as a keyword argument.
vartype – Variable type (see above) may be supplied as a keyword argument.
dtype – Data type.
numpy.float32
andnumpy.float64
are supported. Defaults tonumpy.float64
.
Attributes¶
Adjacency structure as a nested mapping of mappings. |
|
Binary-valued version of the binary quadratic model. |
|
Data-type of the model's biases. |
|
Linear biases as a mapping. |
|
Number of interactions in the model. |
|
Number of variables in the model. |
|
Constant energy offset associated with the model. |
|
Quadratic biases as a flat mapping. |
|
A 2-tuple of |
|
Spin-valued version of the binary quadratic model. |
|
The variables of the binary quadratic model. |
|
The model's variable type. |
Methods¶
|
Add a linear term. |
|
Add a linear constraint as a quadratic objective. |
|
Add variables and linear biases to a binary quadratic model. |
|
Add linear biases from an array-like to a binary quadratic model. |
|
Add a linear inequality constraint as a quadratic objective. |
|
Add a quadratic bias between two variables. |
|
Add quadratic biases to the binary quadratic model. |
|
Add quadratic biases from a square 2d array-like. |
|
Add a variable to a binary quadratic model. |
|
Return a binary quadratic model with the specified vartype. |
|
Enforce u, v being the same variable in a binary quadratic model. |
|
Return a copy. |
|
Return the degree of a variable. |
|
Return the degrees of a binary quadratic model's variables. |
|
Create a new binary quadratic model with no variables and no offset. |
|
Determine the energies of the given samples-like. |
|
Determine the energy of the given sample. |
|
Remove a variable by fixing its value. |
|
Fix the value of the variables and remove them. |
Flip the specified variable in a binary quadratic model. |
|
|
Deserialize a BQM from a Coordinate format encoding. |
|
Construct a binary quadratic model from a file-like object. |
|
Create a binary quadratic model from an Ising problem. |
|
Create a binary quadratic model from NumPy vectors. |
|
Create a binary quadratic model from a QUBO problem. |
|
Deserialize a binary quadratic model. |
|
Test for near equality to all biases of a given binary quadratic model. |
|
Return True if the given model has the same variables, vartypes and biases. |
Return True if the model has no quadratic interactions. |
|
Iterate over the variables and their biases. |
|
Iterate over the neighbors and quadratic biases of a variable. |
|
|
Get the linear bias of a variable. |
|
Get the quadratic bias of a pair of variables. |
Compute a conservative bound on the maximum change in energy that can result from flipping a single variable in a binary quadratic model. |
|
|
Get the total bytes consumed by the biases and indices. |
|
Normalize the biases of a binary quadratic model. |
|
Apply function of two arguments cumulatively to the linear biases. |
|
Apply function of two arguments cumulatively to the quadratic biases associated with a single variable. |
|
Apply function of two arguments cumulatively to the quadratic biases. |
|
Relabel the variables of a binary quadratic model. |
|
Relabel to consecutive integers the variables of a binary quadratic model. |
|
Remove the interaction between a pair of variables. |
|
Remove the given interactions from the binary quadratic model. |
|
Remove the specified variable from a binary quadratic model. |
|
Resize a binary quadratic model to the specified number of variables. |
|
Multiply all biases by the specified scalar. |
|
Set the linear bias of of a variable. |
|
Set the quadratic bias of interaction |
|
Serialize the binary quadratic model to a COOrdinate format encoding. |
|
Serialize the binary quadratic model to a file-like object. |
|
Convert a binary quadratic model to Ising format. |
|
Convert binary quadratic model to 1-dimensional NumPy arrays. |
|
Return a string representing the model as a polynomial. |
|
Convert a binary quadratic model to QUBO format. |
|
Convert the binary quadratic model to a serializable object. |
|
Add the variables, interactions, offset and biases from another binary quadratic model. |
BQM Functions¶
Generic constructor:
|
Convert the input to a binary quadratic model. |
Adding models symbolically:
|
Sum iterable's items. |
Fixing variables:
|
Removed |
Traversing as a graph:
|
Yields sets of connected variables. |
|
Yields variables in breadth-first search order. |
Converting to and from other data structures:
|
Convert a binary quadratic model to NetworkX graph format. |
|
Create a binary quadratic model from a NetworkX graph. |
See also: serialization functions
Discrete Quadratic Models¶
For an introduction to DQMs, see Concepts: Discrete Quadratic Models.
DQM Class¶
- class DiscreteQuadraticModel[source]¶
Encodes a discrete quadratic model.
A discrete quadratic model is a polynomial over discrete variables with terms all of degree two or less.
Examples
This example constructs a map coloring with Canadian provinces. To solve the problem we penalize adjacent provinces having the same color.
>>> provinces = ["AB", "BC", "ON", "MB", "NB", "NL", "NS", "NT", "NU", ... "PE", "QC", "SK", "YT"] >>> borders = [("BC", "AB"), ("BC", "NT"), ("BC", "YT"), ("AB", "SK"), ... ("AB", "NT"), ("SK", "MB"), ("SK", "NT"), ("MB", "ON"), ... ("MB", "NU"), ("ON", "QC"), ("QC", "NB"), ("QC", "NL"), ... ("NB", "NS"), ("YT", "NT"), ("NT", "NU")] >>> colors = [0, 1, 2, 3] ... >>> dqm = dimod.DiscreteQuadraticModel() >>> for p in provinces: ... _ = dqm.add_variable(4, label=p) >>> for p0, p1 in borders: ... dqm.set_quadratic(p0, p1, {(c, c): 1 for c in colors})
The next examples show how to view and manipulate the model biases.
>>> dqm = dimod.DiscreteQuadraticModel()
Add the variables to the model
>>> u = dqm.add_variable(5) # unlabeled variable with 5 cases >>> v = dqm.add_variable(3, label='v') # labeled variable with 3 cases
The linear biases default to 0. They can be read by case or by batch.
>>> dqm.get_linear_case(u, 1) 0.0 >>> dqm.get_linear(u) array([0., 0., 0., 0., 0.]) >>> dqm.get_linear(v) array([0., 0., 0.])
The linear biases can be overwritten either by case or in a batch.
>>> dqm.set_linear_case(u, 3, 17) >>> dqm.get_linear(u) array([ 0., 0., 0., 17., 0.]) >>> dqm.set_linear(v, [0, -1, 3]) >>> dqm.get_linear(v) array([ 0., -1., 3.])
The quadratic biases can also be manipulated sparsely or densely.
>>> dqm.set_quadratic(u, v, {(0, 2): 1.5}) >>> dqm.get_quadratic(u, v) {(0, 2): 1.5} >>> dqm.get_quadratic(u, v, array=True) # as a NumPy array array([[0. , 0. , 1.5], [0. , 0. , 0. ], [0. , 0. , 0. ], [0. , 0. , 0. ], [0. , 0. , 0. ]]) >>> dqm.set_quadratic_case(u, 2, v, 1, -3) >>> dqm.get_quadratic(u, v, array=True) array([[ 0. , 0. , 1.5], [ 0. , 0. , 0. ], [ 0. , -3. , 0. ], [ 0. , 0. , 0. ], [ 0. , 0. , 0. ]]) >>> dqm.get_quadratic(u, v) {(0, 2): 1.5, (2, 1): -3.0}
Attributes¶
The adjacency structure of the variables. |
|
|
Methods¶
|
Add a linear constraint as a quadratic objective. |
|
Add a discrete variable. |
|
Return a copy of the discrete quadratic model. |
|
|
|
|
|
Construct a DQM from a file-like object. |
|
Construct a DQM from five numpy vectors. |
|
The cases of variable v as a sequence |
|
The linear biases associated with variable v. |
|
The linear bias associated with case case of variable v. |
|
The biases associated with the interaction between u and v. |
|
The bias associated with the interaction between two cases of u and v. |
|
If v is provided, the number of cases associated with v, otherwise the total number of cases in the DQM. |
The total number of case interactions. |
|
The total number of variable interactions |
|
The number of variables in the discrete quadratic model. |
|
|
|
|
Relabel the variables of the DQM to integers. |
|
Set the linear biases associated with v. |
|
The linear bias associated with case case of variable v. |
|
Set biases associated with the interaction between u and v. |
|
Set the bias associated with the interaction between two cases of u and v. |
|
Convert the DQM to a file-like object. |
|
Convert the DQM to five numpy vectors and the labels. |
CaseLabelDQM Class¶
- class CaseLabelDQM(*args, **kwargs)[source]¶
DiscreteQuadraticModel that allows assignment of arbitrary labels to cases of discrete variables.
Two types of case labels are offered:
Unique case labels are unique among variable labels and themselves.
Shared case labels are unique among cases for a variable, but may be reused among variables.
Examples
Declare variables with unique case labels.
>>> dqm = dimod.CaseLabelDQM() >>> dqm.add_variable({'x1', 'x2', 'x3'}) 0 >>> dqm.add_variable(['y1', 'y2', 'y3']) 1
Set linear biases
>>> dqm.set_linear('x1', 0.5) >>> dqm.set_linear('y1', 1.5)
Set quadratic biases
>>> dqm.set_quadratic('x2', 'y3', -0.5) >>> dqm.set_quadratic('x3', 'y2', -1.5)
Declare variables with shared case labels.
>>> u = dqm.add_variable({'red', 'green', 'blue'}, shared_labels=True) >>> v = dqm.add_variable(['blue', 'yellow', 'brown'], label='v', shared_labels=True)
Set linear biases
>>> dqm.set_linear_case(u, 'red', 1) >>> dqm.set_linear_case(v, 'yellow', 2)
Set quadratic biases
>>> dqm.set_quadratic_case(u, 'green', v, 'blue', -0.5) >>> dqm.set_quadratic_case(u, 'blue', v, 'brown', -0.5)
Methods¶
|
Add a discrete variable to the model. |
|
The cases of variable v. |
|
The linear biases associated with variable v. |
|
The linear bias associated with case case of variable v. |
|
The biases associated with the interaction between u and v. |
|
The bias associated with the interaction between two cases of u and v. |
|
Transform a sample to reflect case labels. |
|
Set the linear biases associated with v. |
|
The linear bias associated with case case of variable v. |
|
Set biases associated with the interaction between u and v. |
|
Set the bias associated with the interaction between two cases of variables u and v. |