Quadratic Models: Unconstrained¶

The dimod package includes the following unconstrained quadratic models.

Quadratic Models
Binary Quadratic Models
Discrete Quadratic Models

Quadratic Models ¶

Class¶

class QuadraticModel(linear: Optional[Mapping[Hashable, Union[int, float, numpy.number]]] = None, quadratic: Optional[Mapping[Tuple[Hashable, Hashable], Union[int, float, numpy.number]]] = None, offset: Union[int, float, numpy.number] = 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<j} b_{i, j} x_i x_j + c\]

where \(\{ x_i\}_{i=1, \dots, N}\) can be binary or integer variables and \(a_{i}, b_{ij}, c\) are real values.

QM[source]¶: alias of dimod.quadratic.quadratic_model.QuadraticModel

Attributes¶

`adj`	Adjacency structure as a nested mapping of mappings.
`dtype`	Data-type of the model's biases.
`linear`	Linear biases as a mapping.
`num_interactions`	Number of interactions in the model.
`num_variables`	Number of variables in the model.
`offset`	Constant energy offset associated with the model.
`quadratic`	Quadratic biases as a flat mapping.
`shape`	A 2-tuple of `num_variables` and `num_interactions`.
`variables`	The variables of the quadratic model.

Methods¶

`add_linear`(v, bias)	Add a linear bias to an existing variable.
`add_quadratic`(u, v, bias)	Add quadratic bias to a pair of variables.
`add_variable`(vartype[, v, lower_bound, ...])	Add a variable to the quadratic model.
`add_variables_from`(vartype, variables)	Add multiple variables of the same type to the quadratic model.
`change_vartype`(vartype, v)	Change the variable type of the given variable, updating the biases.
`copy`()	Return a copy.
`degree`(v)	Return the degree of specified variable.
`energies`(samples_like[, dtype])	Determine the energies of the given samples-like.
`energy`(sample[, dtype])	Determine the energy of the given sample.
`from_bqm`(bqm)	Construct a quadratic model from a binary quadratic model.
`from_file`(fp)	Construct a QM from a file-like object.
`get_linear`(v)	Get the linear bias of the specified variable.
`get_quadratic`(u, v[, default])	Get the quadratic bias of the specified pair of variables.
`is_almost_equal`(other[, places])	Test if the given quadratic model's biases are almost equal.
`is_equal`(other)	Return True if the given model has the same variables, vartypes and biases.
`is_linear`()	Return True if the model has no quadratic interactions.
`iter_neighborhood`(v)	Iterate over the neighbors and quadratic biases of a variable.
`iter_quadratic`()	Iterate over the interactions of a quadratic model.
`lower_bound`(v)	Return the lower bound on the specified variable.
`set_lower_bound`(v, lb)	Set the lower bound for an integer variable.
`set_upper_bound`(v, ub)	Set the upper bound for an integer variable.
`reduce_linear`(function[, initializer])	Apply function of two arguments cumulatively to the linear biases.
`reduce_neighborhood`(v, function[, initializer])	Apply function of two arguments cumulatively to the quadratic biases associated with a single variable.
`reduce_quadratic`(function[, initializer])	Apply function of two arguments cumulatively to the quadratic biases.
`relabel_variables`(mapping[, inplace])	Relabel the variables according to the given mapping.
`relabel_variables_as_integers`([inplace])	Relabel the variables as [0, n) and return the mapping.
`remove_interaction`(u, v)	Remove the interaction between u and v.
`scale`(scalar)	Scale the biases by the given number.
`set_linear`(v, bias)	Set the linear bias of a variable in the quadratic model.
`set_quadratic`(u, v, bias)	Set the quadratic bias between a pair of variables in the quadratic model.
`spin_to_binary`([inplace])	Convert any spin-valued variables to binary-valued.
`to_file`(*[, spool_size])	Serialize the QM to a file-like object.
`update`(other)	Update the quadratic model from another quadratic model.
`upper_bound`(v)	Return the upper bound on the specified variable.
`vartype`(v)	The variable type of the given variable.

Binary Quadratic Models ¶

For an introduction to BQMs, see Binary Quadratic Models.

Class¶

class BinaryQuadraticModel(*args, offset: Optional[Union[int, float, numpy.number]] = 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.

BQMs can be created in several ways:

BinaryQuadraticModel(vartype)
Create a BQM with no variables or interactions. vartype must be one of:

Vartype.SPIN, 'SPIN', {-1, +1}

Vartype.BINARY, 'BINARY', {0, 1}

BinaryQuadraticModel(bqm)
Create a BQM from another BQM. The resulting BQM will have the same variables, linear biases, quadratic biases and offset as bqm.

BinaryQuadraticModel(bqm, vartype)
Create a BQM from another BQM, changing it to the appropriate vartype if necessary.

BinaryQuadraticModel(n, vartype)
Create a BQM with n variables, indexed linearly from zero, setting all biases to zero.

BinaryQuadraticModel(quadratic, vartype)
Create a BQM from quadratic biases given as a square array_like or a dictionary of the form {(u, v): b, ...}. Note that when formed with SPIN-variables, biases on the diagonal are added to the offset.

BinaryQuadraticModel(linear, quadratic, vartype)
Create a BQM from linear and quadratic biases, where linear is a one-dimensional array_like or a dictionary of the form {v: b, ...}.

BinaryQuadraticModel(linear, quadratic, offset, vartype)
Create a BQM from linear and quadratic biases and an offset. offset must be a number.

Parameters

*args – See above
offset – The offset (see above) may be supplied as a keyword argument.
vartype – The variable type (see above) may be supplied as a keyword argument.
dtype – The data type. numpy.float32 and numpy.float64 are supported. Defaults to numpy.float64.

BQM[source]¶: alias of dimod.binary.binary_quadratic_model.BinaryQuadraticModel

Attributes¶

`adj`	Adjacency structure as a nested mapping of mappings.
`binary`	Binary-valued version of the binary quadratic model.
`dtype`	Data-type of the model's biases.
`linear`	Linear biases as a mapping.
`num_interactions`	Number of interactions in the model.
`num_variables`	Number of variables in the model.
`offset`	Constant energy offset associated with the model.
`quadratic`	Quadratic biases as a flat mapping.
`shape`	A 2-tuple of `num_variables` and `num_interactions`.
`spin`	Spin-valued version of the binary quadratic model.
`variables`	The variables of the binary quadratic model
`vartype`	The model's variable type.

Methods¶

`add_linear`(v, bias)	Add a linear term.
`add_linear_equality_constraint`(terms, ...)	Add a linear constraint as a quadratic objective.
`add_linear_from`(linear)	Add variables and linear biases to a binary quadratic model.
`add_linear_from_array`(linear)	Add linear biases from an array-like to a binary quadratic model.
`add_quadratic`(u, v, bias)	Add a quadratic bias between two variables.
`add_quadratic_from`(quadratic)	Add quadratic biases to the binary quadratic model.
`add_quadratic_from_dense`(quadratic)	Add quadratic biases from a square 2d array-like.
`add_variable`([v, bias])	Add a variable to a binary quadratic model.
`change_vartype`(vartype[, inplace])	Return a binary quadratic model with the specified vartype.
`contract_variables`(u, v)	Enforce u, v being the same variable in a binary quadratic model.
`copy`([deep])	Return a copy.
`degree`(v)	Return the degree of a variable.
`empty`(vartype)	Create a new binary quadratic model with no variables and no offset.
`energies`(samples_like[, dtype])	Determine the energies of the given samples-like.
`energy`(sample[, dtype])	Determine the energy of the given sample.
`fix_variable`(v, value)	Remove a variable by fixing its value.
`fix_variables`(fixed)	Fix the value of the variables and remove them.
`flip_variable`(v)	Flip the specified variable in a binary quadratic model.
`from_coo`(obj[, vartype])	Deserialize a BQM from a Coordinate format encoding.
`from_file`(fp)	Construct a binary quadratic model from a file-like object.
`from_ising`(h, J[, offset])	Create a binary quadratic model from an Ising problem.
`from_numpy_vectors`(linear, quadratic, ...[, ...])	Create a binary quadratic model from NumPy vectors.
`from_qubo`(Q[, offset])	Create a binary quadratic model from a QUBO problem.
`is_almost_equal`(other[, places])	Test if the given binary quadratic model's biases are almost equal.
`is_equal`(other)	Return True if the given model has the same variables, vartypes and biases.
`is_linear`()	Return True if the model has no quadratic interactions.
`iter_neighborhood`(v)	Iterate over the neighbors and quadratic biases of a variable.
`iter_quadratic`([variables])	Iterate over the quadratic biases
`get_linear`(v)	Get the linear bias of a variable.
`get_quadratic`(u, v[, default])	Get the quadratic bias of a pair of variables.
`normalize`([bias_range, quadratic_range, ...])	Normalize the biases of a binary quadratic model.
`reduce_linear`(function[, initializer])	Apply function of two arguments cumulatively to the linear biases.
`reduce_neighborhood`(v, function[, initializer])	Apply function of two arguments cumulatively to the quadratic biases associated with a single variable.
`reduce_quadratic`(function[, initializer])	Apply function of two arguments cumulatively to the quadratic biases.
`relabel_variables`(mapping[, inplace])	Relabel the variables of a binary quadratic model.
`relabel_variables_as_integers`([inplace])	Relabel to consecutive integers the variables of a binary quadratic model.
`remove_interaction`(u, v)	Remove the interaction between a pair of variables.
`remove_interactions_from`(interactions)	Remove the given interactions from the binary quadratic model.
`remove_variable`([v])	Remove the specified variable from a binary quadratic model.
`resize`(n)	Reduce a binary quadratic model to the specified number of variables.
`scale`(scalar[, ignored_variables, ...])	Multiply all the biases by the specified scalar.
`set_linear`(v, bias)	Set the linear bias of of a variable.
`set_quadratic`(u, v, bias)	Set the quadratic bias of variables `(u, v)`.
`to_coo`([fp, vartype_header])	Serialize the binary quadratic model to a COOrdinate format encoding.
`to_file`(*[, ignore_labels, spool_size, version])	Serialize the binary quadratic model to a file-like object.
`to_ising`()	Convert a binary quadratic model to Ising format.
`to_numpy_vectors`([variable_order, dtype, ...])	Save a binary quadratic model as NumPy vectors.
`to_qubo`()	Convert a binary quadratic model to QUBO format.
`update`(other)	Not implemented.

BQM Functions¶

Generic constructor:

as_bqm(*args[, cls, copy, dtype])

Convert the input to a binary quadratic model.

Adding models symbolically:

quicksum(iterable)

Sum iterable's items.

Fixing variables:

fix_variables(bqm[, sampling_mode])

Determine assignments for some variables of a binary quadratic model.

Traversing as a graph:

`connected_components`(bqm)	Yields sets of connected variables.
`bfs_variables`(bqm, source)	Yields variables in breadth-first search order.

Converting to and from other data structures:

`to_networkx_graph`(bqm[, ...])	Convert a binary quadratic model to NetworkX graph format.
`from_networkx_graph`(G[, vartype, ...])	Create a binary quadratic model from a NetworkX graph.

Discrete Quadratic Models ¶

Discrete quadratic models (DQMs) are described under 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¶

`adj`	The adjacency structure of the variables.
`variables`	`Variables` of variable labels.

Methods¶

`add_linear_equality_constraint`(terms, ...)	Add a linear constraint as a quadratic objective.
`add_variable`(num_cases[, label])	Add a discrete variable.
`copy`()	Return a copy of the discrete quadratic model.
`energies`(samples)
`energy`(sample)
`from_file`(file_like)	Construct a DQM from a file-like object.
`from_numpy_vectors`(case_starts, ...[, ...])	Construct a DQM from five numpy vectors.
`get_cases`(v)	The cases of variable v as a sequence
`get_linear`(v)	The linear biases associated with variable v.
`get_linear_case`(v, case)	The linear bias associated with case case of variable v.
`get_quadratic`(u, v[, array])	The biases associated with the interaction between u and v.
`get_quadratic_case`(u, u_case, v, v_case)	The bias associated with the interaction between two cases of u and v.
`num_cases`([v])	If v is provided, the number of cases associated with v, otherwise the total number of cases in the DQM.
`num_case_interactions`()	The total number of case interactions.
`num_variable_interactions`()	The total number of variable interactions
`num_variables`()	The number of variables in the discrete quadratic model.
`relabel_variables`(mapping[, inplace])
`relabel_variables_as_integers`([inplace])	Relabel the variables of the DQM to integers.
`set_linear`(v, biases)	Set the linear biases associated with v.
`set_linear_case`(v, case, bias)	The linear bias associated with case case of variable v.
`set_quadratic`(u, v, biases)	Set biases associated with the interaction between u and v.
`set_quadratic_case`(u, u_case, v, v_case, bias)	Set the bias associated with the interaction between two cases of u and v.
`to_file`([compress, compressed, ...])	Convert the DQM to a file-like object.
`to_numpy_vectors`([return_offset])	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_variable`(cases[, label, shared_labels])	Add a discrete variable to the model.
`get_cases`(v)	The cases of variable v.
`get_linear`(v)	The linear biases associated with variable v.
`get_linear_case`(v, case)	The linear bias associated with case case of variable v.
`get_quadratic`(u, v[, array])	The biases associated with the interaction between u and v.
`get_quadratic_case`(u, u_case, v, v_case)	The bias associated with the interaction between two cases of u and v.
`map_sample`(sample)	Transform a sample to reflect case labels.
`set_linear`(v, biases)	Set the linear biases associated with v.
`set_linear_case`(v, case, bias)	The linear bias associated with case case of variable v.
`set_quadratic`(u, v, biases)	Set biases associated with the interaction between u and v.
`set_quadratic_case`(u, u_case, v, v_case, bias)	Set the bias associated with the interaction between two cases of variables u and v.

Quadratic Models: Unconstrained¶