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

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, *[, default_vartype, ...])

Add a linear bias to an existing variable or a new variable with specified vartype.

add_linear_from(linear, *[, ...])

Add variables and linear biases to a quadratic model.

add_quadratic(u, v, bias)

Add quadratic bias to a pair of variables.

add_quadratic_from(quadratic)

Add quadratic biases.

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.

add_variables_from_model(model, *[, variables])

Add variables from another model.

change_vartype(vartype, v)

Change the variable type of the given variable, updating the biases.

clear()

Remove the offset and all variables and interactions from the model.

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.

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 binary-valued variable.

from_bqm(bqm)

Construct a quadratic model from a binary quadratic model.

from_file(fp)

Construct a quadratic model 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 for near equality to all biases of a given quadratic model.

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_linear()

Iterate over the variables and their biases.

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.

nbytes([capacity])

Get the total bytes consumed by the biases, vartype info, bounds, and indices.

set_lower_bound(v, lb)

Set the lower bound for a variable.

set_upper_bound(v, ub)

Set the upper bound for a 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.

remove_variable([v])

Remove the specified variable from the quadratic model.

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.

to_polystring([encoder])

Return a string representing the model as a polynomial.

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 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 as bqm.

  • BinaryQuadraticModel(bqm, vartype) from an existing BQM, changing to the specified vartype if necessary.

  • BinaryQuadraticModel(n, vartype) with n 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 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_linear_inequality_constraint(terms, ...)

Add a linear inequality constraint as a quadratic objective.

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.

clear()

Remove the offset and all variables and interactions from the model.

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.

degrees([array, dtype])

Return the degrees of a binary quadratic model's variables.

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.

from_serializable(obj)

Deserialize a binary quadratic model.

is_almost_equal(other[, places])

Test for near equality to all biases of a given binary quadratic model.

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_linear()

Iterate over the variables and their biases.

iter_neighborhood(v)

Iterate over the neighbors and quadratic biases of a variable.

get_linear(v)

Get the linear bias of a variable.

get_quadratic(u, v[, default])

Get the quadratic bias of a pair of variables.

maximum_energy_delta()

Compute a conservative bound on the maximum change in energy that can result from flipping a single variable in a binary quadratic model.

nbytes([capacity])

Get the total bytes consumed by the biases and indices.

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)

Resize a binary quadratic model to the specified number of variables.

scale(scalar[, ignored_variables, ...])

Multiply all 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 interaction (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, ...])

Convert binary quadratic model to 1-dimensional NumPy arrays.

to_polystring([encoder])

Return a string representing the model as a polynomial.

to_qubo()

Convert a binary quadratic model to QUBO format.

to_serializable(*[, use_bytes, bias_dtype, ...])

Convert the binary quadratic model to a serializable object.

update(other)

Add the variables, interactions, offset and biases from another binary quadratic model.

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(*args, **kwargs)

Removed

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.

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

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:

  1. Unique case labels are unique among variable labels and themselves.

  2. 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.