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 singlevariable 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 indexlabeled. 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 presolve techniques to be used by the presolver. 

Normalize and presolve the held constraint quadratic model. 
Clear the held constrained quadratic model. 

Return a copy of the held constrained quadratic model. 

Create a 

Return the feasibility of the model. 

Load the default presolvers. 

Normalize the held constrained quadratic model. 


Apply any loaded presolve techniques to the held constrained quadratic model. 

Restore the original variable labels to a set of reduced samples. 

Set the presolve techniques to be used by the presolver. 
Report the presolve techniques to be used by the presolver. 
Feasibility#
TechniqueFlags#
 class TechniqueFlags(value)[source]#
An
IntFlag
to define which presolve techniques will be used by the presolver. 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.
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.

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 currentlyloaded presolve techniques.

explicit Presolver(model_type model)#

enum dwave::presolve::Feasibility#
Values:

enumerator Infeasible#

enumerator Feasible#

enumerator Unknown#

enumerator Infeasible#

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.

enumerator None#