search

dwavesystems / dwavebinarycsp

Map constraint satisfaction problems with binary variables to binary quadratic models.
https://docs.ocean.dwavesys.com/projects/binarycsp/en/latest
Apache License 2.0
20 stars 27 forks source link

ImpossibleBQM error #35

Closed arcondello closed 6 years ago

arcondello commented 6 years ago 
Constraint.from_configurations(frozenset([(0, 1, 1, 0, 1, 0, 1, 0), (0, 1, 0, 0, 0, 1, 0, 1), (0, 1, 0, 1, 0, 1, 1, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 1, 1, 0, 0, 0), (0, 1, 0, 1, 1, 0, 1, 0), (0, 0, 0, 0, 1, 0, 1, 0), (0, 0, 1, 0, 0, 1, 0, 1), (0, 0, 0, 1, 0, 0, 1, 0), (0, 1, 0, 1, 1, 0, 0, 1), (0, 1, 1, 0, 0, 1, 1, 0), (0, 1, 0, 0, 1, 0, 0, 1), (1, 0, 0, 1, 0, 0, 0, 1), (0, 0, 0, 0, 0, 1, 0, 0), (1, 0, 0, 0, 1, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, 1, 0, 1), (0, 0, 0, 0, 0, 1, 1, 0), (0, 0, 1, 0, 1, 0, 0, 1), (0, 1, 1, 0, 1, 0, 0, 1), (0, 1, 0, 0, 0, 1, 1, 0), (0, 1, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 0, 0), (0, 1, 0, 0, 0, 1, 0, 0), (0, 0, 0, 0, 1, 0, 0, 1), (0, 0, 1, 0, 0, 1, 1, 0), (1, 0, 1, 0, 0, 0, 0, 1), (0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 1, 0, 0, 1, 0, 0), (0, 1, 0, 0, 1, 0, 1, 0), (0, 1, 0, 0, 1, 0, 0, 0), (0, 0, 0, 1, 0, 1, 1, 0), (0, 0, 0, 0, 0, 1, 0, 1), (0, 0, 1, 0, 1, 0, 1, 0), (1, 0, 0, 0, 0, 0, 0, 1), (0, 0, 0, 1, 0, 1, 0, 0), (0, 0, 1, 0, 1, 0, 0, 0), (1, 0, 0, 1, 0, 0, 1, 0), (0, 0, 0, 1, 1, 0, 1, 0), (0, 1, 1, 0, 0, 1, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 0, 0, 0), (1, 0, 1, 0, 0, 0, 0, 0), (0, 1, 0, 1, 0, 0, 0, 1), (0, 1, 0, 0, 0, 0, 1, 0), (1, 0, 0, 1, 1, 0, 0, 0), (0, 0, 1, 0, 0, 0, 1, 0), (0, 1, 1, 0, 0, 0, 1, 0), (0, 1, 1, 0, 0, 0, 0, 1), (0, 0, 0, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 1), (1, 0, 0, 0, 0, 0, 1, 0), (0, 1, 0, 1, 0, 1, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1), (1, 0, 1, 0, 1, 0, 1, 0), (1, 0, 0, 0, 0, 1, 0, 1), (0, 0, 0, 1, 1, 0, 0, 1), (0, 1, 0, 1, 0, 0, 1, 0), (0, 1, 0, 0, 0, 0, 0, 1), (0, 1, 0, 1, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 0), (1, 0, 0, 1, 1, 0, 0, 1), (1, 0, 1, 0, 0, 1, 1, 0), (1, 0, 0, 0, 1, 0, 0, 1), (1, 0, 0, 1, 1, 0, 1, 0), (1, 0, 1, 0, 0, 0, 1, 0), (0, 1, 1, 0, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (1, 0, 1, 0, 1, 0, 0, 1), (1, 0, 0, 0, 0, 1, 1, 0), (1, 0, 0, 1, 0, 1, 0, 1), (0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 1, 0, 0), (0, 1, 1, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 1), (0, 1, 1, 0, 1, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 1), (1, 0, 0, 0, 1, 0, 1, 0), (1, 0, 0, 1, 0, 1, 1, 0)]), ('AB0', 'BC0', 'AB1', 'BC1', 'AB2', 'BC2', 'AB3', 'BC3'), Vartype.BINARY, name='Constraint')

This is a reducible constraint, but each of the four components can be mapped to two variables. So this should be able to be stitched to a bqm over 8 variables.

arcondello commented 6 years ago

For a csp with only the above constraint

In [15]: bqm = dwavebinarycsp.stitch(csp, max_graph_size=9)

In [16]: bqm
Out[16]: BinaryQuadraticModel({'BC3': 0.0, 'BC2': 0.0, 'BC0': 0.0, 'BC1': 0.0, 'AB3': 0.0, 'AB1': 0.0, 'AB2': 0.0, 'AB0': 0.0}, {('AB3', 'AB0'): 0.0, ('BC2', 'AB2'): 4.0, ('BC3', 'AB0'): 0.0, ('AB3', 'BC0'): 0.0, ('BC2', 'AB1'): 0.0, ('BC0', 'AB0'): 4.0, ('BC3', 'BC0'): 0.0, ('BC3', 'AB3'): 4.0, ('BC3', 'BC2'): 0.0, ('BC1', 'AB2'): 0.0, ('BC0', 'AB2'): 0.0, ('AB3', 'AB2'): 0.0, ('BC1', 'AB1'): 4.0, ('BC0', 'AB1'): 0.0, ('AB3', 'AB1'): 0.0, ('BC0', 'BC1'): 0.0, ('AB3', 'BC1'): 0.0, ('BC3', 'BC1'): 0.0, ('AB2', 'AB0'): 0.0, ('AB1', 'AB2'): 0.0, ('BC2', 'AB0'): 0.0, ('AB1', 'AB0'): 0.0, ('BC1', 'BC2'): 0.0, ('BC0', 'BC2'): 0.0, ('BC3', 'AB2'): 0.0, ('AB3', 'BC2'): 0.0, ('BC1', 'AB0'): 0.0, ('BC3', 'AB1'): 0.0}, -4.0, Vartype.BINARY)