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.