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 [1] [2].

[1]

Boros, E., P.L. Hammer, G. Tavares. Preprocessing of Unconstraint Quadratic Binary Optimization. Rutcor Research Report 10-2006, April, 2006.

[2]

Boros, E., P.L. Hammer. Pseudo-Boolean optimization. Discrete Applied Mathematics 123, (2002), pp. 155-225.

roof_duality(bqm, *, strict=True)

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.