dimod.roof_duality.fix_variables

fix_variables(bqm, sampling_mode=True)[source]

Determine assignments for some variables of a binary quadratic model.

Roof duality finds a lower bound for the minimum of a quadratic polynomial. It can also find minimizing assignments for some of the polynomial’s variables; these fixed variables take the same values in all optimal solutions [BHT] [BH]. A quadratic pseudo-Boolean function can be represented as a network to find the lower bound through network-flow computations. fix_variables uses maximum flow in the implication network to correctly fix variables. Consequently, you can find an assignment for the remaining variables that attains the optimal value.

Parameters:
  • bqm (BinaryQuadraticModel) – A binary quadratic model.
  • sampling_mode (bool, optional, default=True) – In sampling mode, only roof-duality is used. When sampling_mode is false, strongly connected components are used to fix more variables, but in some optimal solutions these variables may take different values.
Returns:

Variable assignments for some variables of the specified binary quadratic model.

Return type:

dict

Examples

This example creates a binary quadratic model with a single ground state and fixes the model’s single variable to the minimizing assignment.

>>> bqm = dimod.BinaryQuadraticModel.from_ising({'a': 1.0}, {})
>>> dimod.fix_variables(bqm)
{'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)
>>> dimod.fix_variables(bqm) # doctest: +SKIP
{}

This example turns sampling model off, 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)
>>> dimod.fix_variables(bqm, sampling_mode=False) # doctest: +SKIP
{'a': 1, 'b': 1}
[BHT]Boros, E., P.L. Hammer, G. Tavares. Preprocessing of Unconstraint Quadratic Binary Optimization. Rutcor Research Report 10-2006, April, 2006.
[BH]Boros, E., P.L. Hammer. Pseudo-Boolean optimization. Discrete Applied Mathematics 123, (2002), pp. 155-225