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.load_default_presolvers()
>>> presolve.apply()

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: dimod.constrained.constrained.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.load_default_presolvers()
>>> presolver.apply()

The model is reduced.

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

Methods¶

`apply`()	Apply any loaded presolve techniques to the held constrained 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.
`load_default_presolvers`	Load the default presolvers.
`restore_samples`	Restore the original variable labels to a set of reduced samples.

C++ API¶

template<class Bias, class Index, class Assignment> class Presolver¶

Public Functions

Presolver()¶: Default constructor.

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

void apply()¶: Apply any loaded presolve techniques. Acts of the model() in-place.

model_type detach_model()¶

Detach the constrained quadratic model and return it.

This clears the model from the presolver.

void load_default_presolvers()¶: Load the default presolve techniques.

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

const Postsolver<bias_type, index_type, assignment_type> &postsolver() const¶: Return a const reference to the held postsolver.

template<class Bias, class Index, class Assignment> class Postsolver¶

Public Functions

template<class T> std::vector<T> apply(std::vector<T> reduced) const¶: Return a sample of the original CQM from a sample of the reduced CQM.