dwavesystems / dwavesystems/dimod

`DQM.from_bqm` or similar

Open
#945 1 comment 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

Something like
```python
import warnings

from typing import Collection, Dict, Hashable, Mapping, Optional, Tuple

import dimod

try:
from dimod.typing import Variable
except ImportError:
# dimod < 0.10
Variable = Hashable

def bqm_to_dqm(bqm: dimod.BinaryQuadraticModel,
one_hots: Optional[Collection[Collection[Variable]]] = None,
) -> Tuple[dimod.DiscreteQuadraticModel, Dict[Variable, Tuple[Variable, int]]]:
"""Convert a BQM into a DQM.

Args:
bqm: A binary quadratic model.
one_hots: a collection of one-hot constraints. Each one-hot constraint
should cover a set of BQM variables. The one-hot constraints
cannot overlap

Returns:
A 2-tuple:

dqm: A discrete quadratic model
mapping: A mapping from the variable of the bqm to the `(variable, case)`
in the dqm.

"""
if bqm.vartype is dimod.SPIN:
raise ValueError("given bqm must be binary")

dqm = dimod.DiscreteQuadraticModel()
mapping: Dict[Variable, Tuple[Variable, int]] = dict()

if one_hots is not None:
for c, constraint in enumerate(one_hots):
if len(constraint) == 1:
# this is just binary
continue

dqm.add_variable(num_cases=len(constraint), label=c)

for case, v in enumerate(constraint):
if v in mapping:
raise ValueError("one-hot constraints must be disjoint")
mapping[v] = (c, case)

for v in bqm.variables:
if v not in mapping:
# variables that are not included in a one-hot constraint are
# added as two-case variables
dqm.add_variable(2, label=v)
mapping[v] = (v, 1) # track the case that indicates v is true

dqm.set_linear_case(*mapping[v], bqm.get_linear(v))

for u, v, bias in bqm.iter_quadratic():
if mapping[u][0] == mapping[v][0]:
# we can ignore interactions within a one-hot constraint
continue
dqm.set_quadratic_case(*mapping[u], *mapping[v], bias)

try:
# dimod 0.10 supports offsets, just ignore it for older versions
dqm.offset += bqm.offset
except AttributeError:
if bqm.offset:
warnings.warn('bqm has an offset that is ignored', stacklevel=2)

return dqm, mapping

def dqm_sample_to_bqm_sample(sample: Mapping[Variable, int],
mapping: Mapping[Variable, Tuple[Variable, int]],
) -> Dict[Variable, int]:
"""Convert a DQM sample into a BQM sample according to the given mapping
from BQM variables to DQM variables."""
return dict((bqm_v, int(sample[dqm_v] == case)) for bqm_v, (dqm_v, case) in mapping.items())

```

some basic unittests

```python
import unittest

class Test(unittest.TestCase):
def test_no_onehot(self):
bqm = dimod.generators.gnp_random_bqm('abcdefghijkl', .25, 'SPIN')
bqm.change_vartype('BINARY', inplace=True)
bqm.offset = 0 # zero the offset out since not all dimod versions support it in DQM

dqm, mapping = bqm_to_dqm(bqm)

bqm_sampleset = dimod.ExactSolver().sample(bqm)
dqm_sampleset = dimod.ExactDQMSolver().sample_dqm(dqm)

# this assumes that the lowest is unique. todo: fix
self.assertEqual(dqm_sampleset.first.sample,
dqm_sample_to_bqm_sample(dqm_sampleset.first.sample, mapping))

def test_with_onehot(self):
bqm = dimod.generators.gnp_random_bqm('abcdefghijkl', .25, 'SPIN')
bqm.change_vartype('BINARY', inplace=True)
bqm.offset = 0 # zero the offset out since not all dimod versions support it in DQM

one_hots = [['a', 'b', 'c', 'd'], ['k', 'f']]

dqm, mapping = bqm_to_dqm(bqm, one_hots)

bqm_sampleset = dimod.ExactSolver().sample(bqm)
dqm_sampleset = dimod.ExactDQMSolver().sample_dqm(dqm)

# find the lowest-energy bqm sample that satisfies the one-hot
for sample in bqm_sampleset.samples():
if all(sum(sample[v] for v in const) == 1 for const in one_hots):
# this assumes that the lowest is unique. todo: fix
self.assertEqual(sample,
dqm_sample_to_bqm_sample(dqm_sampleset.first.sample, mapping))
break
```

the first snippet should work with dimod 0.9 but the tests require 0.10.

*Additional Context*
For `CaseLabelDQM`, we would not need to return the mapping.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.