Quadratic Models: Unconstrained

The dimod package includes the following unconstrained 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.

See also: serialization functions

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:

  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.