Decomposers#

Classes#

class ComponentDecomposer(rolling=True, silent_rewind=True, key=None, reverse=None, **runopts)[source]#

Selects a subproblem of variables that make up a connected component.

Parameters:

rolling (bool, optional, default=True) – If True, successive calls for the same problem (with possibly different samples) produce subproblems on different components, selected by rolling down the list of all components.
key (callable, optional, default=None) – Extracts a comparison key from each component of the problem. The comparison keys determine which component will be used to build the subproblem.
reverse (bool, optional, default=None) – Only applies when key is specified. If False, the components’ comparison keys will be sorted in increasing order. If True or unspecified, they will be sorted in decreasing order.
silent_rewind (bool, optional, default=True) – If False, raises EndOfStream when resetting/rewinding the subproblem generator once all components have been used.

class EnergyImpactDecomposer(size, min_gain=None, rolling=True, rolling_history=1.0, silent_rewind=True, traversal='energy', **runopts)[source]#

Selects a subproblem of variables maximally contributing to the problem energy.

The selection currently implemented does not ensure that the variables are connected in the problem graph.

Parameters:

size (int) – Nominal number of variables in the subproblem. Actual subproblem can be smaller, depending on other parameters (e.g. min_gain).
min_gain (int, optional, default=-inf) – Minimum reduction required to BQM energy, given the current sample. A variable is included in the subproblem only if inverting its sample value reduces energy by at least this amount.
rolling (bool, optional, default=True) – If True, successive calls for the same problem (with possibly different samples) produce subproblems on different variables, selected by rolling down the list of all variables sorted by decreasing impact.
rolling_history (float, optional, default=1.0) – Fraction of the problem size, as a float in range 0.0 to 1.0, that should participate in the rolling selection. Once reached, subproblem unrolling is reset.
silent_rewind (bool, optional, default=True) – If False, raises EndOfStream when resetting/rewinding the subproblem generator upon the reset condition for unrolling.
traversal (str, optional, default='energy') –
Traversal algorithm used to pick a subproblem of size variables. Options are:

energy:
Use the next size variables in the list of variables ordered by descending energy impact.

bfs:
Breadth-first traversal seeded by the next variable in the energy impact list.

pfs:
Priority-first traversal seeded by variables from the energy impact list, proceeding with the variable on the search boundary that has the highest energy impact.

See Examples.

class IdentityDecomposer[source]#: Selects a subproblem that is a full copy of the problem.

class RandomConstraintDecomposer(size, constraints, **runopts)[source]#

Selects variables randomly as constrained by groupings.

By grouping related variables, the problem’s structure can guide the random selection of variables so subproblems are related to the problem’s constraints.

Parameters:

size (int) – Number of variables in the subproblem.
constraints (list[set]) – Groups of variables in the BQM, as a list of sets, where each set is associated with a constraint.

See Examples.

class RandomSubproblemDecomposer(size, **runopts)[source]#

Selects a subproblem of size random variables.

The selection currently implemented does not ensure that the variables are connected in the problem graph.

Parameters:: size (int) – Number of variables in the subproblem.

See Examples.

class RoofDualityDecomposer(sampling_mode=True, **runopts)[source]#

Selects a subproblem with variables that cannot be fixed by roof duality.

Roof duality finds a lower bound for the minimum of a quadratic polynomial. It can also find minimizing assignments for some of the polynomial’s variables; these fixed variables take the same values in all optimal solutions [BHT] [BH]. A quadratic pseudo-Boolean function can be represented as a network to find the lower bound through network-flow computations. This decomposer can also use maximum flow in the implication network to fix variables. Consequently, you can find an assignment for the remaining variables that attains the optimal value.

Parameters:: sampling_mode (bool, optional, default=True) – In sampling mode, only roof-duality is used. When sampling_mode is false, strongly connected components are used to fix more variables, but in some optimal solutions these variables may take different values.

[BHT]

Boros, E., P.L. Hammer, G. Tavares. Preprocessing of Unconstraint Quadratic Binary Optimization. Rutcor Research Report 10-2006, April, 2006.

[BH]

Boros, E., P.L. Hammer. Pseudo-Boolean optimization. Discrete Applied Mathematics 123, (2002), pp. 155-225

class TilingChimeraDecomposer(size=(4, 4, 4), loop=True, **runopts)[source]#

Returns sequential Chimera lattices that tile the initial problem.

A Chimera lattice is an m-by-n grid of Chimera tiles, where each tile is a bipartite graph with shores of size t. The problem is decomposed into a sequence of subproblems with variables belonging to the Chimera lattices that tile the problem Chimera lattice. For example, a 2x2 Chimera lattice could be tiled 64 times (8x8) on a fully-yielded D-Wave 2000Q system (16x16).

Parameters:

size (int, optional, default=(4,4,4)) – Size of the Chimera lattice as (m, n, t), where m is the number of rows, n the columns, and t the size of shore in the Chimera lattice.
loop (Bool, optional, default=True) – Cycle continually through the tiles.

See Examples.

class SublatticeDecomposer(seed=None, **runopts)[source]#

Selects a lattice-structured subproblem.

This decomposer requires the input state to contain fields bqm and origin_embeddings; only the keys (the variables/nodes) from origin_embeddings are used. The decomposer can also use the optional state fields problem_dims, exclude_dims, geometric_offset and origin_embedding_index.

By default geometric_offset is assigned uniformly at random on the range given by problem_dims. By default origin_embedding_index is assigned uniformly at random on the range [0,len(state.origin_embeddings)). The random number generator can be initialized with the class variable seed.

If problem_dims is a state field, geometrically offset variables are wrapped around boundaries according to assumed periodic boundary condition. This is a required field when the geometric_offset is not specified. Note that, the origin embedding must specify a lattice smaller than the target lattice.

Parameters:: seed (int, default=None) – Pseudo-random number generator seed.
Returns:: subproblem and embedding state fields

Methods#

make_origin_embeddings([qpu_sampler, ...])

Creates optimal embeddings for a lattice.

Examples#

ComponentDecomposer#

This example iterates twice on a 4-variable binary quadratic model, decomposing the problem into 2 connected components which are selected by component size in decreasing order.

import dimod
from hybrid.decomposers import ComponentDecomposer
from hybrid.core import State
from hybrid.utils import random_sample

bqm = dimod.BinaryQuadraticModel({'a': 1, 'b': -1, 'c': 1, 'd': 2}, {'ab': 1, 'bc': 1}, 0, dimod.SPIN)
state0 = State.from_sample(random_sample(bqm), bqm)

decomposer = ComponentDecomposer(key=len)
state1 = decomposer.next(state0).result()
state2 = decomposer.next(state1).result()

>>> print(state1.subproblem)
BinaryQuadraticModel({b: -1.0, a: 1.0, c: 1.0}, {('b', 'a'): 1.0, ('b', 'c'): 1.0}, 0.0, 'SPIN')
>>> print(state2.subproblem)
BinaryQuadraticModel({d: 2.0}, {}, 0.0, 'SPIN')

EnergyImpactDecomposer#

This example iterates twice on a 10-variable binary quadratic model with a random initial sample set. size configuration limits the subproblem in the first iteration to the first 4 variables shown in the output of flip_energy_gains.

import dimod
from hybrid.decomposers import EnergyImpactDecomposer
from hybrid.core import State
from hybrid.utils import min_sample, flip_energy_gains

bqm = dimod.BinaryQuadraticModel({t: 0 for t in range(10)},
                                 {(t, (t+1) % 10): 1 for t in range(10)},
                                 0, 'BINARY')

decomposer = EnergyImpactDecomposer(size=4, rolling=True, rolling_history=1.0)
state0 = State.from_sample(min_sample(bqm), bqm)

>>> flip_energy_gains(bqm, state0.samples.first.sample)
[(0, 9), (0, 8), (0, 7), (0, 6), (0, 5), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0)]
>>> state1 = decomposer.run(state0).result()
>>> list(state1.subproblem.variables)
[8, 7, 9, 6]
>>> state2 = decomposer.run(state1).result()
>>> list(state2.subproblem.variables)
[2, 3, 4, 5]

RandomSubproblemDecomposer#

This example decomposes a 6-variable binary quadratic model with a random initial sample set to create a 3-variable subproblem.

import dimod
from hybrid.decomposers import RandomSubproblemDecomposer
from hybrid.core import State
from hybrid.utils import random_sample

bqm = dimod.BinaryQuadraticModel(
    {t: 0 for t in range(6)}, {(t, (t+1) % 6): 1 for t in range(6)}, 0, 'BINARY')

decomposer = RandomSubproblemDecomposer(bqm, size=3)
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()

>>> print(state1.subproblem)
BinaryQuadraticModel({2: 1.0, 3: 0.0, 4: 0.0}, {(2, 3): 1.0, (3, 4): 1.0}, 0.0, Vartype.BINARY)

TilingChimeraDecomposer#

This example decomposes a 2048-variable Chimera structured binary quadratic model read from a file into 2x2x4-lattice subproblems.

import dimod
from hybrid.decomposers import TilingChimeraDecomposer
from hybrid.core import State
from hybrid.utils import random_sample

with open('problems/random-chimera/2048.09.qubo', 'r') as fp:
    bqm = dimod.BinaryQuadraticModel.from_coo(fp)

decomposer = TilingChimeraDecomposer(size=(2,2,4))
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()

>>> print(state1.subproblem)
BinaryQuadraticModel({0: 0.0, 4: 0.0, 5: 0.0, 6: 0.0, 7: -3.0, 1: 0.0, 2: 0.0, 3: -4.0, 1024: -7.0, 1028: 0.0,
>>> # Snipped above response for brevity
>>> state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({8: 3.0, 12: 0.0, 13: 2.0, 14: -11.0, 15: -3.0, 9: 4.0, 10: 0.0, 11: 0.0, 1032: 0.0,
>>> # Snipped above response for brevity

RandomConstraintDecomposer#

This example decomposes a 4-variable binary quadratic model that represents three serial NOT gates into 2-variable subproblems. The expected decomposition should use variables that represent one of the NOT gates rather than two arbitrary variables.

import dimod
from hybrid.decomposers  RandomConstraintDecomposer
from hybrid.core import State
from hybrid.utils import random_sample

bqm = dimod.BinaryQuadraticModel({'w': -2.0, 'x': -4.0, 'y': -4.0, 'z': -2.0},
                                 {('w', 'x'): 4.0, ('x', 'y'): 4.0, ('y', 'z'): 4.0},
                                 3.0, 'BINARY')

decomposer = RandomConstraintDecomposer(2, [{'w', 'x'}, {'x', 'y'}, {'y', 'z'}])
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()

>>> print(state1.subproblem)
BinaryQuadraticModel({'z': -2.0, 'y': 0.0}, {('z', 'y'): 4.0}, 0.0, Vartype.BINARY)

SublatticeDecomposer#

This example creates a 5x5 square ferromagnetic lattice problem, and builds the 3x3 subproblem located at the center of the square. The initial state is set to all spin up. Only the variable (2,2) is not adjacent to the boundary, other variables pick up a linear bias of 1 or 2 due to the boundary condition. Keys of the origin embedding dict determine the subproblem created, in this case there is no minor-embedding provided (values are empty).

import dimod
from hybrid.decomposers import SublatticeDecomposer
from hybrid.core import State

problem_dims = (5, 5)
subproblem_dims = (3, 3)
geometric_offset = (1, 1)
edgelist = [((i, j), (i+1, j))
    for i in range(problem_dims[0]-1)
    for j in range(problem_dims[1])]
edgelist += [((i, j), (i, j+1))
    for i in range(problem_dims[0])
    for j in range(problem_dims[1]-1)]
bqm = dimod.BinaryQuadraticModel({}, {edge: -1 for edge in edgelist},
                                 0, dimod.SPIN)
origin_embeddings = [{(i, j): None
    for i in range(subproblem_dims[0])
    for j in range(subproblem_dims[1])}]
decomposer = SublatticeDecomposer()
sample = {var: 1 for var in bqm.variables}
state0 = State.from_sample(sample, bqm,
                           origin_embeddings=origin_embeddings,
                           problem_dims=problem_dims,
                           geometric_offset=geometric_offset)

state1 = decomposer.run(state0).result()

>>> print(state1.subproblem)
BinaryQuadraticModel({(1, 2): -1.0, (2, 2): 0.0, (1, 1): -2.0, (1, 3): -2.0, (2, 1): -1.0, (3, 1): -2.0, (3, 2): -1.0, (2, 3): -1.0, (3, 3): -2.0}, {((1, 2), (2, 2)): 1.0, ((1, 2), (1, 1)): 1.0, ((1, 2), (1, 3)): 1.0, ((2, 2), (2, 1)): 1.0, ((2, 2), (2, 3)): 1.0, ((2, 2), (3, 2)): 1.0, ((1, 1), (2, 1)): 1.0, ((1, 3), (2, 3)): 1.0, ((2, 1), (3, 1)): 1.0, ((3, 1), (3, 2)): 1.0, ((3, 2), (3, 3)): 1.0, ((2, 3), (3, 3)): 1.0}, 0.0, 'SPIN')