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.
See Examples.

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:
 Breadthfirst traversal seeded by the next variable in the energy impact list.
 pfs:
 Priorityfirst 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
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: 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 pseudoBoolean function can be represented as a network to find the lower bound through networkflow 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 roofduality 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 102006, April, 2006. [BH] Boros, E., P.L. Hammer. PseudoBoolean optimization. Discrete Applied Mathematics 123, (2002), pp. 155225

class
TilingChimeraDecomposer
(size=(4, 4, 4), loop=True, **runopts)[source]¶ Returns sequential Chimera lattices that tile the initial problem.
A Chimera lattice is an mbyn 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 fullyyielded DWave 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.
Examples¶
ComponentDecomposer¶
This example iterates twice on a 4variable 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 10variable 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 6variable binary quadratic model with a random initial sample set to create a 3variable 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 2048variable Chimera structured binary quadratic model read from a file into 2x2x4lattice subproblems.
import dimod
from hybrid.decomposers import TilingChimeraDecomposer
from hybrid.core import State
from hybrid.utils import random_sample
with open('problems/randomchimera/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 4variable binary quadratic model that represents three serial NOT gates into 2variable 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)