API Reference#

Composites#

The dwave-preprocessing package includes several composites.

Added in version 0.6.8: Support for context manager protocol and close() method.

Context-manager usage pattern is recommended for samplers and composites that allocate scope-bound resources, such as DWaveSampler.

>>> with ClipComposite(DWaveSampler()) as sampler:      
...     sampler.sample(...)

Clip#

Class#

class ClipComposite(child_sampler)[source]#

Composite to clip variables of a problem.

Clips the variables of a binary quadratic model (BQM) and modifies linear and quadratic terms accordingly.

Parameters:: sampler (dimod.Sampler) – A dimod sampler.

Examples

This example uses ClipComposite to instantiate a composed sampler that submits a simple Ising problem to a sampler. The composed sampler clips linear and quadratic biases as indicated by options.

>>> from dimod import ExactSolver
>>> from dwave.preprocessing.composites import ClipComposite
>>> h = {'a': -4.0, 'b': -4.0}
>>> J = {('a', 'b'): 3.2}
>>> sampler = ClipComposite(ExactSolver())
>>> response = sampler.sample_ising(h, J, lower_bound=-2.0, upper_bound=2.0)

Properties#

`child`	The child sampler.
`children`	List of child samplers that that are used by this composite.
`parameters`	Parameters as a dict, where keys are keyword parameters accepted by the sampler methods and values are lists of the properties relevent to each parameter.
`properties`	Properties as a dict containing any additional information about the sampler.

Methods#

`sample`(bqm, *[, lower_bound, upper_bound])	Clip and sample from the provided binary quadratic model.
`sample_ising`(h, J, **parameters)	Sample from an Ising model using the implemented sample method.
`sample_qubo`(Q, **parameters)	Sample from a QUBO using the implemented sample method.

Connected Components#

Class#

class ConnectedComponentsComposite(child_sampler)[source]#

Composite to decompose a problem to the connected components and solve each.

Connected components of a binary quadratic model (BQM) graph are computed (if not provided), and each subproblem is passed to the child sampler. Returned samples from each child sampler are merged. Only the best solution of each response is selected and merged with others (i.e. this composite returns a single solution).

Parameters:: sampler (dimod.Sampler) – A dimod sampler

Examples

This example uses ConnectedComponentsComposite to solve a simple Ising problem that can be separated into two components. This small example uses dimod.ExactSolver and is just illustrative.

>>> from dimod import ExactSolver
>>> from dwave.preprocessing.composites import ConnectedComponentsComposite
>>> h = {}
>>> J1 = {(1, 2): -1.0, (2, 3): 2.0, (3, 4): 3.0}
>>> J2 = {(12, 13): 6}
>>> sampler = ExactSolver()
>>> sampler_ccc = ConnectedComponentsComposite(sampler)
>>> e1 = sampler.sample_ising(h, J1).first.energy
>>> e2 = sampler.sample_ising(h, J2).first.energy
>>> e_ccc = sampler_ccc.sample_ising(h, {**J1, **J2}).first.energy
>>> e_ccc == e1 + e2
True

Properties#

`child`	The child sampler.
`children`	List of child samplers that that are used by this composite.
`parameters`	Parameters as a dict, where keys are keyword parameters accepted by the sampler methods and values are lists of the properties relevent to each parameter.
`properties`	Properties as a dict containing any additional information about the sampler.

Methods#

`sample`(bqm, *[, components])	Sample from the provided binary quadratic model.
`sample_ising`(h, J, **parameters)	Sample from an Ising model using the implemented sample method.
`sample_qubo`(Q, **parameters)	Sample from a QUBO using the implemented sample method.

Fix Variables#

Class#

class FixVariablesComposite(child_sampler, *, algorithm='explicit')[source]#

Composite to fix variables of a problem to provided.

Fixes variables of a binary quadratic model (BQM) and modifies linear and quadratic terms accordingly. Returned samples include the fixed variable.

Parameters:

child_sampler (dimod.Sampler) – A dimod sampler
algorithm (str, optional, default='explicit') –
Determines how fixed_variables are found.

’explicit’: fixed_variables should be passed in a call to .sample(). If not, no fixing occurs and the problem is directly passed to the child sampler.

’roof_duality’: Roof duality algorithm is used to find fixed_variables. strict may be passed in a call to .sample() to determine what variables the algorithm will fix. For details, see roof_duality().

Examples

This example uses the FixVariablesComposite to instantiate a composed sampler that submits a simple Ising problem to a sampler. The composed sampler fixes a variable and modifies linear and quadratic biases accordingly.

>>> from dimod import ExactSolver
>>> from dwave.preprocessing.composites import FixVariablesComposite
>>> h = {1: -1.3, 4: -0.5}
>>> J = {(1, 4): -0.6}
>>> sampler = FixVariablesComposite(ExactSolver())
>>> sampleset = sampler.sample_ising(h, J, fixed_variables={1: -1})

This next example involves the same problem but calculates fixed_variables using the ‘roof_duality’ algorithm.

>>> sampler = FixVariablesComposite(ExactSolver(), algorithm='roof_duality')
>>> sampleset = sampler.sample_ising(h, J, strict=False)

Properties#

`child`	The child sampler.
`children`	List of child samplers that that are used by this composite.
`parameters`	Parameters as a dict, where keys are keyword parameters accepted by the sampler methods and values are lists of the properties relevent to each parameter.
`properties`	Properties as a dict containing any additional information about the sampler.

Methods#

`sample`(bqm, **parameters)	Sample from the provided binary quadratic model.
`sample_ising`(h, J, **parameters)	Sample from an Ising model using the implemented sample method.
`sample_qubo`(Q, **parameters)	Sample from a QUBO using the implemented sample method.

Scale#

Class#

class ScaleComposite(child_sampler)[source]#

Composite that scales variables of a problem.

Scales the variables of a binary quadratic model (BQM) and modifies linear and quadratic terms accordingly.

Parameters:: sampler (dimod.Sampler) – A dimod sampler.

Examples

This example uses ScaleComposite to instantiate a composed sampler that submits a simple Ising problem to a sampler. The composed sampler scales linear biases, quadratic biases, and offset as indicated by options.

>>> from dimod import ExactSolver
>>> from dwave.preprocessing.composites import ScaleComposite
>>> h = {'a': -4.0, 'b': -4.0}
>>> J = {('a', 'b'): 3.2}
>>> sampler = ScaleComposite(ExactSolver())
>>> response = sampler.sample_ising(h, J, scalar=0.5,
...                ignored_interactions=[('a','b')])

Properties#

`child`	The child sampler.
`children`	List of child samplers that that are used by this composite.
`parameters`	Parameters as a dict, where keys are keyword parameters accepted by the sampler methods and values are lists of the properties relevent to each parameter.
`properties`	Properties as a dict containing any additional information about the sampler.

Methods#

`sample`(bqm, *[, scalar, bias_range, ...])	Scale and sample from the provided binary quadratic model.
`sample_ising`(h, J, **parameters)	Sample from an Ising model using the implemented sample method.
`sample_qubo`(Q, **parameters)	Sample from a QUBO using the implemented sample method.

Spin Reversal Transform#

Class#

class SpinReversalTransformComposite(child: Sampler, *, seed=None)[source]#

Composite for applying spin reversal transform preprocessing.

A spin-reversal transform can improve sample statistics when the sampler is a physical object with asymmetries such as a QPU. The technique works as follows: given an \(n\)-variable Ising problem, the composite selects a random \(g\in\{\pm1\}^n\) and transforms the problem via \(h_i\mapsto h_ig_i\) and \(J_{ij}\mapsto J_{ij}g_ig_j\). Solutions \(s\) of the original problem and \(s^\prime\) of the transformed problem are related by \(s^\prime_i=s_ig_i\) and have identical energies. [1]

Note

If you are configuring an anneal schedule, be mindful that this composite does not recognize the initial_state parameter used by dimod’s DWaveSampler for reverse annealing (composites do not generally process all keywords of child samplers) and does not flip any of the configured initial states.

Parameters:

sampler – A dimod sampler object.
seed – As passed to numpy.random.default_rng().

Examples

This example composes a dimod ExactSolver sampler with spin transforms then uses it to sample an Ising problem.

>>> from dimod import ExactSolver
>>> from dwave.preprocessing.composites import SpinReversalTransformComposite
>>> base_sampler = ExactSolver()
>>> composed_sampler = SpinReversalTransformComposite(base_sampler)
... # Sample an Ising problem
>>> response = composed_sampler.sample_ising({'a': -0.5, 'b': 1.0}, {('a', 'b'): -1})
>>> response.first.sample
{'a': -1, 'b': -1}

References

Properties#

`child`	The child sampler.
`children`	List of child samplers that that are used by this composite.
`parameters`	Parameters as a dict, where keys are keyword parameters accepted by the sampler methods and values are lists of the properties relevent to each parameter.
`properties`	Properties as a dict containing any additional information about the sampler.

Methods#

`sample`(bqm, *[, num_spin_reversal_transforms])	Sample from the binary quadratic model.
`sample_ising`(h, J, **parameters)	Sample from an Ising model using the implemented sample method.
`sample_qubo`(Q, **parameters)	Sample from a QUBO using the implemented sample method.

Lower Bounds#

A common preprocessing method for binary quadratic models (BQM) is finding the lower bound of their energy.

Roof Duality#

dwave-preprocessing contains an implementation of roof duality, an algorithm used for finding a lower bound for the minimum of a quadratic boolean function, as well as minimizing assignments for some of the boolean variables; these fixed variables take the same values in all, or some, optimal solutions [Bor2006] [Bor2002].

roof_duality(bqm, *, strict=True)[source]#

Determine a lower bound for a binary quadratic model’s energy, as well as minimizing assignments for some of its variables, using the roof duality algorithm.

Parameters:

bqm (BinaryQuadraticModel) – A binary quadratic model.
strict (bool, optional, default=True) – If True, only fixes variables for which assignments are true for all minimizing points (strong persistency). If False, also fixes variables for which the assignments are true for some but not all minimizing points (weak persistency).

Returns:

float: Lower bound for the energy of bqm.

dict: Variable assignments for some variables of bqm.

Return type:

(float, dict) A 2-tuple containing

Examples

This example creates a binary quadratic model with a single ground state and finds both an energy lower bound and a minimizing assignment to the model’s single variable.

>>> import dimod
>>> from dwave.preprocessing.lower_bounds import roof_duality
>>> bqm = dimod.BinaryQuadraticModel.from_ising({'a': 1.0}, {})
>>> roof_duality(bqm)
(-1.0, {'a': -1})

This example has two ground states, \(a=b=-1\) and \(a=b=1\), with no variable having a single value for all ground states, so neither variable is fixed.

>>> bqm = dimod.BinaryQuadraticModel.empty(dimod.SPIN)
>>> bqm.add_interaction('a', 'b', -1.0)
>>> roof_duality(bqm) 
(-1.0, {})

This example sets strict to False, so variables are fixed to an assignment that attains the ground state.

>>> bqm = dimod.BinaryQuadraticModel.empty(dimod.SPIN)
>>> bqm.add_interaction('a', 'b', -1.0)
>>> roof_duality(bqm, strict=False) 
(-1.0, {'a': -1, 'b': -1})

The roof duality algorithm may also be accessed through the FixVariablesComposite.

CQM Presolve#

A class for presolve algorithms.

Presolve algorithms enhance performance and solution quality by performing preprocessing to reduce a problem’s redundant variables and constraints and to improve the accuracy of the CQM.

The purpose of the following example is to show how to locally run the presolve algorithms provided here prior to submitting your CQM to a solver, such as the LeapHybridCQMSampler.

This example uses a simplified problem for illustrative purposes: a CQM with just a single-variable objective and constraint. This is sufficient to show how to run Presolver methods.

The CQM created below has a constraint requiring that integer variable j not exceed 5.

>>> import dimod
...
>>> j = dimod.Integer("j")
>>> cqm = dimod.ConstrainedQuadraticModel()
>>> cqm.set_objective(j)
>>> cqm.add_constraint(j <= 5, "Maximum j")
'Maximum j'

Clearly, the global optimum for this CQM occurs for the default value of the lower bound of j.

>>> cqm.lower_bound("j")
0.0

To run Ocean’s presolve algorithms locally, instantiate a Presolver on your CQM and apply a supported presolve (default is used here).

>>> from dwave.preprocessing.presolve import Presolver
...
>>> presolve = Presolver(cqm)
>>> presolve.apply()
True

You now have a preprocessed CQM you can submit to a CQM solver such as a Leap CQM solver.

>>> reduced_cqm = presolve.detach_model()
>>> print(reduced_cqm.constraints)
{}

The dimod ExactCQMSolver test solver is capable of solving this very simple CQM.

>>> sampleset = dimod.ExactCQMSolver().sample_cqm(reduced_cqm)
>>> print(sampleset.first)
Sample(sample={0: 0}, energy=0.0, num_occurrences=1, is_satisfied=array([], dtype=bool), is_feasible=True)

View the solution as assignments of the original CQM’s variables:

>>> presolve.restore_samples(sampleset.first.sample)
(array([[0.]]), Variables(['j']))

You can also create the sample set for the original CQM:

>>> restored_sampleset = dimod.SampleSet.from_samples_cqm(presolve.restore_samples(sampleset.samples()), cqm)
>>> print(restored_sampleset)
    j energy num_oc. is_sat. is_fea.
0 0.0    0.0       1 arra...    True
1 1.0    1.0       1 arra...    True
2 2.0    2.0       1 arra...    True
3 3.0    3.0       1 arra...    True
4 4.0    4.0       1 arra...    True
5 5.0    5.0       1 arra...    True
['INTEGER', 6 rows, 6 samples, 1 variables]

Presolver#

Class#

class Presolver(cqm: ConstrainedQuadraticModel, *, move: bool = False)[source]#

Presolver for constrained quadratic models.

The model held by this class to represent the instantiating constrained quadratic model (CQM) is index-labeled. This is because presolve may remove, add, change the type of, and substitute variables. Consequently, while the models remain mathematically equivalent, variables of the original and reduced CQMs may not have a direct relationship.

Parameters:

cqm – A dimod.ConstrainedQuadraticModel.
move – If True, the original CQM is cleared and its contents are moved to the presolver. This is useful for large models where memory is a concern.

Example

This example reduces an implicitly fixed constraint.

>>> import dimod
>>> from dwave.preprocessing import Presolver

Create a simple CQM with one variable fixed by bounds.

>>> cqm = dimod.ConstrainedQuadraticModel()
>>> i = dimod.Integer('i', lower_bound=-5, upper_bound=5)
>>> j = dimod.Integer('j', lower_bound=5, upper_bound=10)
>>> cqm.set_objective(i + j)
>>> c0 = cqm.add_constraint(j <= 5)  # implicitly fixes 'j'

Run presolve with default settings.

>>> presolver = Presolver(cqm)
>>> presolver.apply()
True

The model is reduced.

>>> reduced_cqm = presolver.detach_model()
>>> reduced_cqm.num_variables()
1
>>> reduced_cqm.num_constraints()
0

Methods#

`add_techniques`(techniques)	Add presolve techniques to be used by the presolver.
`apply`()	Normalize and presolve the held constraint quadratic model.
`clear_model`()	Clear the held constrained quadratic model.
`copy_model`()	Return a copy of the held constrained quadratic model.
`detach_model`()	Create a `dimod.ConstrainedQuadraticModel` from the held model.
`feasibility`()	Return the feasibility of the model.
`load_default_presolvers`()	Load the default presolvers.
`normalize`()	Normalize the held constrained quadratic model.
`presolve`([time_limit_s])	Apply any loaded presolve techniques to the held constrained quadratic model.
`restore_samples`(samples_like)	Restore the original variable labels to a set of reduced samples.
`set_techniques`(techniques)	Set the presolve techniques to be used by the presolver.
`techniques`()	Report the presolve techniques to be used by the presolver.

Feasibility#

class Feasibility(value)[source]#

An Enum to signal whether a model is feasible or not.

Infeasible[source]#: The model is known to be infeasible

Feasible[source]#: The model is known to be feasible

Unknown[source]#: It is not known if the model is feasible or not

TechniqueFlags#

class TechniqueFlags(value)[source]#

An IntFlag to define which presolve techniques will be used by the presolver.

None_[source]#: No techniques.

RemoveRedundantConstraints[source]#: Remove redundant constraints. See Achterberg et al., section 3.1.

RemoveSmallBiases[source]#: Remove small biases from the objective and constraints. See Achterberg et al., section 3.1.

DomainPropagation[source]#: Use constraints to tighten the bounds on variables. See Achterberg et al., section 3.2.

All[source]#: All techniques.

Default[source]#: Currently equivalent to All, though this may change in the future.

C++ API#

template<class Bias, class Index = int, class Assignment = Bias> class Presolver#

Public Functions

explicit Presolver(model_type model)#: Construct a presolver from a constrained quadratic model.

TechniqueFlags add_techniques(TechniqueFlags techniques)#: Add presolve techniques to be run. This will not affect existing loaded techniques.

bool apply()#: Apply any loaded presolve techniques. Acts on the model() in-place.

model_type detach_model()#

Detach the constrained quadratic model and return it.

This clears the model from the presolver.

const model_type &model() const#: Return a const reference to the held constrained quadratic model.

bool normalize()#: Normalize the model.

bool presolve()#: Presolve a normalized model.

std::vector<assignment_type> restore(std::vector<assignment_type> reduced) const#: Return a sample of the original CQM from a sample of the reduced CQM.

TechniqueFlags set_techniques(TechniqueFlags techniques)#: Set the presolve techniques to be run.

TechniqueFlags techniques() const#: Return the currently-loaded presolve techniques.

enum dwave::presolve::Feasibility#

Values:

enumerator Infeasible#

enumerator Feasible#

enumerator Unknown#

enum dwave::presolve::TechniqueFlags#

Values:

enumerator None#

enumerator RemoveRedundantConstraints#

Remove redundant constraints.

See Achterberg et al., section 3.1.

enumerator RemoveSmallBiases#

Remove small biases from the objective and constraints.

See Achterberg et al., section 3.1.

enumerator DomainPropagation#

Use constraints to tighten the bounds on variables.

See Achterberg et al., section 3.2.

enumerator All#: All techniques.

enumerator Default#: Currently equivalent to All, though this may change in the future.

C++ API#

Functions#

template<class V, class B> std::pair<double, std::vector<std::pair<int, int>>> fix_variables_::fixQuboVariables(dimod::BinaryQuadraticModel<B, V> &bqm, bool strict, double offset = 0.0)#

Fixes the variables of an BinaryQuadraticModel.

Parameters:

bqm – BinaryQuadraticModel to find minimizing variable assignments for
strict – When true, only the variables corresponding to strong persistencies are fixed. When false, the function tries to fix all the variables corresponding to strong and weak persistencies. Also when false, variables that do not contribute any coefficient to the posiform are set to 1. This may happen if their bias in the original QUBO was 0 or if they were flushed to zero when converted to the posiform.
offset – The bqm’s offset, used to calculate the lower bound. Defaults to 0.

template<class PosiformInfo> capacity_type fix_variables_::fixQuboVariables(PosiformInfo &posiform_info, int num_bqm_variables, bool strict, std::vector<std::pair<int, int>> &fixed_variables)#

Fixes the QUBO variables.

Parameters:

posiform_info – Object containing information needed to recreate a posiform corresponding to QUBO.
num_bqm_variables – Number of variables in the original QUBO.
strict – When true, only the variables corresponding to strong persistencies are fixed. When false, the function tries to fix all the variables corresponding to strong and weak persistencies. Also when false, variables that do not contribute any coefficient to the posiform are set to 1. This may happen if their bias in the original QUBO was 0 or if they were flushed to zero when converted to the posiform.
fixed_variables – Variables to fix.

Classes#

template<class BQM, class coefficient_t> class PosiformInfo#

Contains all the information needed to recreate a posiform corresponding to a BQM.

The intention is to reduce the memory footprint as much as possible, thus requiring some processing before the stored data can be used.

For implementation details, see comments in the source code.

For details on the algorithm, see : Boros, Endre & Hammer, Peter & Tavares, Gabriel. (2006). Preprocessing of unconstrained quadratic binary optimization. RUTCOR Research Report.

Public Functions

PosiformInfo(const BQM &bqm)#: Construct a PosiformInfo from a binary quadratic model.

inline int getNumVariables()#: Get number of posiform variables.

inline int getNumLinear()#: Get number of posiform variables with a non-zero linear bias.

inline coefficient_type getLinear(int posiform_variable)#: Get the linear bias of a posiform variable.

inline int getNumQuadratic(int posiform_variable)#: Get number of quadratic terms a posiform variable contributes in.

inline std::pair<quadratic_iterator_type, quadratic_iterator_type> getQuadratic(int posiform_variable)#: Get the neighbors of a posiform variable in the corresponding BQM.

inline int mapVariableQuboToPosiform(int bqm_variable)#

Map a QUBO variable to a posiform variable.

The number of QUBO variables and posiform variables may differ since the coefficient for a QUBO variable may turn out to be zero in a posiform. This may occur if the coefficient is flushed to zero during the conversion or if the variable did not have non-zero linear/quadratic biases in the QUBO.

inline int mapVariablePosiformToQubo(int posiform_variable)#

Map a posiform variable to a QUBO variable.

inline coefficient_type convertToPosiformCoefficient(bias_type bqm_bias)#: Convert a QUBO coefficient to a posiform coefficient.

inline double getBiasConversionRatio()#: Return the value by which bqm biases are multiplied to get posiform coefficients.

inline double getConstant()#: Return the value of the constant term of the posiform.

void print()#: Print out posiform details.