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 pseudoBoolean function can be represented as a network to find the lower bound through networkflow 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 roofduality 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: 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 102006, April, 2006. [BH] Boros, E., P.L. Hammer. PseudoBoolean optimization. Discrete Applied Mathematics 123, (2002), pp. 155225  bqm (