D-Waveの制約式をイジングモデルに変換するライブラリの仕組みを追ってみた ref: https://qiita.com/piyo7/items/5782576aa97b7449a3cf

file0.txt

a, b, c \in \{-1, 1\} \\
abc = 1 \\
a+b+c < 3

file1.txt

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)

file10.txt

"""
.. [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
"""

file11.txt

@pm.penaltymodel_factory(-150)
def get_penalty_model(specification):
    """Factory function for penaltymodel-mip.
...
    Raises:
        :class:`penaltymodel.ImpossiblePenaltyModel`: If the penalty cannot be built.

file12.txt

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)

file13.txt

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}

file14.txt

bqm = dwavebinarycsp.stitch(csp, min_classical_gap=.1)

print(bqm)

file15.txt

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)

file16.txt

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]

file17.sh

$ 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     

file2.txt

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)

file3.txt

\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

file4.txt

print(csp.constraints)

file5.txt

[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')]

file6.txt

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

file7.txt

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

file8.txt

@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.

file9.txt

@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.