dwavebinarycsp.stitch

stitch(csp, min_classical_gap=2.0, max_graph_size=8)

Build a binary quadratic model with minimal energy levels at solutions to the specified constraint satisfaction problem.

Parameters:

• csp (ConstraintSatisfactionProblem) – Constraint satisfaction problem.

• min_classical_gap (float, optional, default=2.0) – Minimum energy gap from ground. Each constraint violated by the solution increases the energy level of the binary quadratic model by at least this much relative to ground energy.

• max_graph_size (int, optional, default=8) – Maximum number of variables in the binary quadratic model that can be used to represent a single constraint.

Returns:

BinaryQuadraticModel

Notes

For a min_classical_gap > 2 or constraints with more than two variables, requires access to factories from the penaltymodel ecosystem to construct the binary quadratic model.

Examples

This example creates a binary-valued constraint satisfaction problem with two constraints, \(a = b\) and \(b \ne c\), and builds a binary quadratic model such that each constraint violation by a solution adds the default minimum energy gap.

>>> import operator
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(operator.eq, ['a', 'b'])  # a == b
>>> csp.add_constraint(operator.ne, ['b', 'c'])  # b != c
>>> bqm = dwavebinarycsp.stitch(csp)

Variable assignments that satisfy the CSP above, violate one, then two constraints, produce energy increases of the default minimum classical gap:

>>> bqm.energy({'a': 0, 'b': 0, 'c': 1})  
-2.0
>>> bqm.energy({'a': 0, 'b': 0, 'c': 0})  
0.0
>>> bqm.energy({'a': 1, 'b': 0, 'c': 0}) 
2.0

This example creates a binary-valued constraint satisfaction problem with two constraints, \(a = b\) and \(b \ne c\), and builds a binary quadratic model with a minimum energy gap of 4. Note that in this case the conversion to binary quadratic model adds two ancillary variables that must be minimized over when solving.

>>> import operator
>>> import itertools
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(operator.eq, ['a', 'b'])  # a == b
>>> csp.add_constraint(operator.ne, ['b', 'c'])  # b != c
>>> bqm = dwavebinarycsp.stitch(csp, min_classical_gap=4.0)
>>> list(bqm)   
['a', 'aux1', 'aux0', 'b', 'c']

Variable assignments that satisfy the CSP above, violate one, then two constraints, produce energy increases of the specified minimum classical gap:

>>> min([bqm.energy({'a': 0, 'b': 0, 'c': 1, 'aux0': aux0, 'aux1': aux1}) for
... aux0, aux1 in list(itertools.product([0, 1], repeat=2))])  
-6.0
>>> min([bqm.energy({'a': 0, 'b': 0, 'c': 0, 'aux0': aux0, 'aux1': aux1}) for
... aux0, aux1 in list(itertools.product([0, 1], repeat=2))])  
-2.0
>>> min([bqm.energy({'a': 1, 'b': 0, 'c': 0, 'aux0': aux0, 'aux1': aux1}) for
... aux0, aux1 in list(itertools.product([0, 1], repeat=2))])  
2.0

This example finds for the previous example the minimum graph size.

>>> import operator
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(operator.eq, ['a', 'b'])  # a == b
>>> csp.add_constraint(operator.ne, ['b', 'c'])  # b != c
>>> for n in range(8, 1, -1):
...     try:
...         bqm = dwavebinarycsp.stitch(csp, min_classical_gap=4.0, max_graph_size=n)
...     except dwavebinarycsp.exceptions.ImpossibleBQM:
...         print(n+1)
...
3