Last active
January 1, 2019 11:22
-
-
Save piyo7/e98d6e7e63c15773f57e9fc5efef088f to your computer and use it in GitHub Desktop.
D-Waveの制約式をイジングモデルに変換するライブラリの仕組みを追ってみた ref: https://qiita.com/piyo7/items/5782576aa97b7449a3cf
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
a, b, c \in \{-1, 1\} \\ | |
abc = 1 \\ | |
a+b+c < 3 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import dwavebinarycsp | |
csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.SPIN) | |
csp.add_constraint(lambda a, b, c: a * b * c == 1, ['a', 'b', 'c']) | |
csp.add_constraint(lambda a, b, c: a + b + c < 3, ['a', 'b', 'c']) | |
bqm = dwavebinarycsp.stitch(csp) | |
print(bqm) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
.. [DO] Bian et al., "Discrete optimization using quantum annealing on sparse Ising models", | |
https://www.frontiersin.org/articles/10.3389/fphy.2014.00056/full | |
.. [MC] Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, and A. Roy | |
"Mapping constrained optimization problems to quantum annealing with application to fault diagnosis" | |
https://arxiv.org/pdf/1603.03111.pdf | |
""" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@pm.penaltymodel_factory(-150) | |
def get_penalty_model(specification): | |
"""Factory function for penaltymodel-mip. | |
... | |
Raises: | |
:class:`penaltymodel.ImpossiblePenaltyModel`: If the penalty cannot be built. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import dimod | |
import itertools | |
res = dimod.ExactSolver().sample(bqm) | |
min_energy = next(res.data(sorted_by='energy')).energy | |
for sample in itertools.takewhile(lambda sample: sample.energy == min_energy, res.data(sorted_by='energy')): | |
print(csp.check(sample.sample), sample.energy, sample.sample) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
True -7.0 {'a': 1, 'aux0': -1, 'aux1': -1, 'aux2': -1, 'b': -1, 'c': -1} | |
True -7.0 {'a': 1, 'aux0': -1, 'aux1': -1, 'aux2': 1, 'b': -1, 'c': -1} | |
True -7.0 {'a': -1, 'aux0': 1, 'aux1': 1, 'aux2': 1, 'b': -1, 'c': 1} | |
True -7.0 {'a': -1, 'aux0': 1, 'aux1': 1, 'aux2': -1, 'b': -1, 'c': 1} | |
True -7.0 {'a': -1, 'aux0': 1, 'aux1': 1, 'aux2': 1, 'b': 1, 'c': -1} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
bqm = dwavebinarycsp.stitch(csp, min_classical_gap=.1) | |
print(bqm) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
BinaryQuadraticModel({'a': -0.5, 'aux0': -1.0, 'b': 1.5, 'c': 0.5, 'aux1': -1.0}, {('aux0', 'a'): 1.0, ('b', 'a'): -0.5, ('b', 'aux0'): -1.0, ('c', 'a'): 0.5, ('c', 'aux0'): -1.0, ('c', 'b'): 0.5, ('aux1', 'a'): 1.0, ('b', 'aux1'): -1.0, ('c', 'aux1'): 1.0}, 0.0, Vartype.SPIN) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Specification(object): | |
... | |
def __init__(self, graph, decision_variables, feasible_configurations, vartype, | |
ising_linear_ranges=None, | |
ising_quadratic_ranges=None): | |
... | |
linear_ranges[v] = [-2, 2] | |
... | |
quad_ranges[u][v] = quad_ranges[v][u] = [-1, 1] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ python --version | |
Python 3.7.0 | |
$ pip list | grep -e dwavebinarycsp -e penaltymodel -e dimod | |
dimod 0.7.9 | |
dwavebinarycsp 0.0.9 | |
penaltymodel 0.15.3 | |
penaltymodel-cache 0.3.2 | |
penaltymodel-maxgap 0.4.1 | |
penaltymodel-mip 0.1.3 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
BinaryQuadraticModel({'a': -1.0, 'aux0': -2.0, 'aux1': 0.0, 'b': 2.0, 'c': 1.0, 'aux2': -1.0}, {('aux0', 'a'): 1.0, ('aux1', 'a'): 1.0, ('aux1', 'aux0'): -1.0, ('b', 'a'): -1.0, ('b', 'aux0'): -1.0, ('b', 'aux1'): -1.0, ('c', 'a'): 0.0, ('c', 'aux0'): -1.0, ('c', 'aux1'): -1.0, ('c', 'b'): 1.0, ('aux2', 'a'): 1.0, ('b', 'aux2'): -1.0, ('c', 'aux2'): 1.0}, 0.0, Vartype.SPIN) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\newcommand{\argmin}{\mathop{\rm arg~min}\limits} | |
\argmin_{a, b, c \in \{-1, 1\}} -a+2b+c-2x-z-ab+bc+ax+ay+az-bx-by-bz-cx-cy+cz-xy |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
print(csp.constraints) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
[Constraint.from_configurations(frozenset({(1, -1, -1), (1, 1, 1), (-1, -1, 1), (-1, 1, -1)}), ('a', 'b', 'c'), Vartype.SPIN, name='Constraint'), Constraint.from_configurations(frozenset({(1, 1, -1), (-1, 1, 1), (1, -1, -1), (-1, -1, 1), (1, -1, 1), (-1, 1, -1), (-1, -1, -1)}), ('a', 'b', 'c'), Vartype.SPIN, name='Constraint')] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Constraint(Sized): | |
... | |
def from_func(cls, func, variables, vartype, name=None): | |
... | |
configurations = frozenset(config | |
for config in itertools.product(vartype.value, repeat=len(variables)) | |
if func(*config)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def stitch(csp, min_classical_gap=2.0, max_graph_size=8): | |
... | |
bqm = dimod.BinaryQuadraticModel.empty(csp.vartype) | |
... | |
for const in csp.constraints: | |
... | |
pmodel = None | |
... | |
for G in iter_complete_graphs(const.variables, max_graph_size + 1, aux): | |
# construct a specification | |
spec = pm.Specification( | |
graph=G, | |
decision_variables=const.variables, | |
feasible_configurations=configurations, | |
vartype=csp.vartype | |
) | |
# try to use the penaltymodel ecosystem | |
try: | |
pmodel = pm.get_penalty_model(spec) | |
except pm.ImpossiblePenaltyModel: | |
# hopefully adding more variables will make it possible | |
continue | |
if pmodel.classical_gap >= min_classical_gap: | |
break | |
... | |
bqm.update(pmodel.model) | |
return bqm |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@pm.interface.penaltymodel_factory(100) | |
def get_penalty_model(specification, database=None): | |
"""Factory function for penaltymodel_cache. | |
... | |
Raises: | |
:class:`penaltymodel.MissingPenaltyModel`: If the penalty model is not in the | |
cache. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@pm.penaltymodel_factory(-100) # set the priority to low | |
def get_penalty_model(specification): | |
"""Factory function for penaltymodel_maxgap. | |
... | |
Raises: | |
:class:`penaltymodel.ImpossiblePenaltyModel`: If the penalty cannot be built. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment