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) 
{}

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) 
{'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