# Copyright 2019 D-Wave Systems Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
# ============================================================================
from __future__ import division
import itertools
import collections.abc as abc
from numbers import Number
import numpy as np
from dimod.decorators import vartype_argument
from dimod.sampleset import as_samples
from dimod.utilities import iter_safe_relabels
from dimod.vartypes import Vartype
__all__ = 'BinaryPolynomial',
def asfrozenset(term):
"""Convert to frozenset if it is not already"""
return term if isinstance(term, frozenset) else frozenset(term)
[docs]class BinaryPolynomial(abc.MutableMapping):
"""A polynomial with binary variables and real-valued coefficients.
Args:
poly (mapping/iterable):
Polynomial as a mapping of form {term: bias, ...}, where `term` is
a collection of variables and `bias` the associated bias. It can also
be an iterable of 2-tuples (term, bias).
vartype (:class:`.Vartype`/str/set):
Variable type for the binary quadratic model. Accepted input values:
* :class:`.Vartype.SPIN`, ``'SPIN'``, ``{-1, 1}``
* :class:`.Vartype.BINARY`, ``'BINARY'``, ``{0, 1}``
Attributes:
degree (int):
The degree of the polynomial.
variables (set):
The variables.
vartype (:class:`.Vartype`):
One of :class:`.Vartype.SPIN` or :class:`.Vartype.BINARY`.
Examples:
Binary polynomials can be constructed in many different ways. The
following are all equivalent
>>> poly = dimod.BinaryPolynomial({'a': -1, 'ab': 1}, dimod.SPIN)
>>> poly = dimod.BinaryPolynomial({('a',): -1, ('a', 'b'): 1}, dimod.SPIN)
>>> poly = dimod.BinaryPolynomial([('a', -1), (('a', 'b'), 1)], dimod.SPIN)
>>> poly = dimod.BinaryPolynomial({'a': -1, 'ab': .5, 'ba': .5}, dimod.SPIN)
Binary polynomials act a mutable mappings but the terms can be accessed with
any sequence.
>>> poly = dimod.BinaryPolynomial({'a': -1, 'ab': 1}, dimod.BINARY)
>>> poly['ab']
1
>>> poly['ba']
1
>>> poly[{'a', 'b'}]
1
>>> poly[('a', 'b')]
1
>>> poly['cd'] = 4
>>> poly['dc']
4
"""
@vartype_argument('vartype')
def __init__(self, poly, vartype):
if isinstance(poly, abc.Mapping):
poly = poly.items()
# we need to aggregate the repeated terms
self._terms = terms = {}
for term, bias in poly:
fsterm = asfrozenset(term)
# when SPIN-valued, s^2 == 1, so we need to handle that case
# in BINARY, x^2 == x
if len(fsterm) < len(term) and vartype is Vartype.SPIN:
new = set()
term = tuple(term) # make sure it has .count
for v in fsterm:
if term.count(v) % 2:
new.add(v)
fsterm = frozenset(new)
if fsterm in terms:
terms[fsterm] += bias
else:
terms[fsterm] = bias
self.vartype = vartype
def __contains__(self, term):
return asfrozenset(term) in self._terms
def __delitem__(self, term):
del self._terms[asfrozenset(term)]
def __eq__(self, other):
if not isinstance(other, BinaryPolynomial):
try:
other = type(self)(other, self.vartype)
except Exception:
# not a polynomial
return False
if self.vartype != other.vartype:
return False
for term, bias in self.items():
if bias and other[term] != bias:
return False
for term, bias in other.items():
if bias and self[term] != bias:
return False
return True
def __ne__(self, other):
return not (self == other)
def __getitem__(self, term):
return self._terms[asfrozenset(term)]
def __iter__(self):
return iter(self._terms)
def __len__(self):
return len(self._terms)
def __setitem__(self, term, bias):
self._terms[asfrozenset(term)] = bias
def __repr__(self):
return '{!s}({!r}, {!r})'.format(self.__class__.__name__,
self._terms, self.vartype.name)
@property
def variables(self):
"""Variables of the polynomial."""
return set().union(*self._terms)
@property
def degree(self):
"""Degree of the polynomial."""
if len(self) == 0:
return 0
return max(map(len, self._terms))
[docs] def copy(self):
"""Create a shallow copy."""
return type(self)(self, self.vartype)
[docs] def energy(self, sample_like, dtype=np.float):
"""The energy of the given sample.
Args:
sample_like (samples_like):
A raw sample. `sample_like` is an extension of
NumPy's array_like structure. See :func:`.as_samples`.
dtype (:class:`numpy.dtype`, optional):
The data type of the returned energies. Defaults to float.
Returns:
The energy.
"""
energy, = self.energies(sample_like, dtype=dtype)
return energy
[docs] def energies(self, samples_like, dtype=np.float):
"""The energies of the given samples.
Args:
samples_like (samples_like):
A collection of raw samples. `samples_like` is an extension of
NumPy's array_like structure. See :func:`.as_samples`.
dtype (:class:`numpy.dtype`, optional):
The data type of the returned energies. Defaults to float.
Returns:
:obj:`numpy.ndarray`: The energies.
"""
samples, labels = as_samples(samples_like)
if labels:
idx, label = zip(*enumerate(labels))
labeldict = dict(zip(label, idx))
else:
labeldict = {}
num_samples = samples.shape[0]
energies = np.zeros(num_samples, dtype=dtype)
for term, bias in self.items():
if len(term) == 0:
energies += bias
else:
energies += np.prod([samples[:, labeldict[v]] for v in term], axis=0) * bias
return energies
[docs] def relabel_variables(self, mapping, inplace=True):
"""Relabel variables of a binary polynomial as specified by mapping.
Args:
mapping (dict):
Dict mapping current variable labels to new ones. If an
incomplete mapping is provided, unmapped variables retain their
current labels.
inplace (bool, optional, default=True):
If True, the binary polynomial is updated in-place; otherwise, a
new binary polynomial is returned.
Returns:
:class:`.BinaryPolynomial`: A binary polynomial with the variables
relabeled. If `inplace` is set to True, returns itself.
"""
if not inplace:
return self.copy().relabel_variables(mapping, inplace=True)
for submap in iter_safe_relabels(mapping, self.variables):
for oldterm, bias in list(self.items()):
newterm = frozenset((submap.get(v, v) for v in oldterm))
if newterm != oldterm:
self[newterm] = bias
del self[oldterm]
return self
[docs] def normalize(self, bias_range=1, poly_range=None, ignored_terms=None):
"""Normalizes the biases of the binary polynomial such that they fall in
the provided range(s).
If `poly_range` is provided, then `bias_range` will be treated as
the range for the linear biases and `poly_range` will be used for
the range of the other biases.
Args:
bias_range (number/pair):
Value/range by which to normalize the all the biases, or if
`poly_range` is provided, just the linear biases.
poly_range (number/pair, optional):
Value/range by which to normalize the higher order biases.
ignored_terms (iterable, optional):
Biases associated with these terms are not scaled.
"""
def parse_range(r):
if isinstance(r, Number):
return -abs(r), abs(r)
return r
if ignored_terms is None:
ignored_terms = set()
else:
ignored_terms = {asfrozenset(term) for term in ignored_terms}
if poly_range is None:
linear_range, poly_range = bias_range, bias_range
else:
linear_range = bias_range
lin_range, poly_range = map(parse_range, (linear_range, poly_range))
# determine the current ranges for linear, higherorder
lmin = lmax = 0
pmin = pmax = 0
for term, bias in self.items():
if term in ignored_terms:
# we don't use the ignored terms to calculate the scaling
continue
if len(term) == 1:
lmin = min(bias, lmin)
lmax = max(bias, lmax)
elif len(term) > 1:
pmin = min(bias, pmin)
pmax = max(bias, pmax)
inv_scalar = max(lmin / lin_range[0], lmax / lin_range[1],
pmin / poly_range[0], pmax / poly_range[1])
if inv_scalar != 0:
self.scale(1 / inv_scalar, ignored_terms=ignored_terms)
[docs] def scale(self, scalar, ignored_terms=None):
"""Multiply the polynomial by the given scalar.
Args:
scalar (number):
Value to multiply the polynomial by.
ignored_terms (iterable, optional):
Biases associated with these terms are not scaled.
"""
if ignored_terms is None:
ignored_terms = set()
else:
ignored_terms = {asfrozenset(term) for term in ignored_terms}
for term in self:
if term not in ignored_terms:
self[term] *= scalar
[docs] @classmethod
def from_hising(cls, h, J, offset=None):
"""Construct a binary polynomial from a higher-order Ising problem.
Args:
h (dict):
The linear biases.
J (dict):
The higher-order biases.
offset (optional, default=0.0):
Constant offset applied to the model.
Returns:
:obj:`.BinaryPolynomial`
Examples:
>>> poly = dimod.BinaryPolynomial.from_hising({'a': 2}, {'ab': -1}, 0)
>>> poly.degree
2
"""
poly = {(k,): v for k, v in h.items()}
poly.update(J)
if offset is not None:
poly[frozenset([])] = offset
return cls(poly, Vartype.SPIN)
[docs] def to_hising(self):
"""Construct a higher-order Ising problem from a binary polynomial.
Returns:
tuple: A 3-tuple of the form (`h`, `J`, `offset`) where `h` includes
the linear biases, `J` has the higher-order biases and `offset` is
the linear offset.
Examples:
>>> poly = dimod.BinaryPolynomial({'a': -1, 'ab': 1, 'abc': -1}, dimod.SPIN)
>>> h, J, off = poly.to_hising()
>>> h
{'a': -1}
"""
if self.vartype is Vartype.BINARY:
return self.to_spin().to_hising()
h = {}
J = {}
offset = 0
for term, bias in self.items():
if len(term) == 0:
offset += bias
elif len(term) == 1:
v, = term
h[v] = bias
else:
J[tuple(term)] = bias
return h, J, offset
[docs] @classmethod
def from_hubo(cls, H, offset=None):
"""Construct a binary polynomial from a higher-order unconstrained
binary optimization (HUBO) problem.
Args:
H (dict):
Coefficients of a higher-order unconstrained binary optimization
(HUBO) model.
Returns:
:obj:`.BinaryPolynomial`
Examples:
>>> poly = dimod.BinaryPolynomial.from_hubo({('a', 'b', 'c'): -1})
>>> poly.degree
3
"""
poly = cls(H, Vartype.BINARY)
if offset is not None:
poly[()] = poly.get((), 0) + offset
return poly
[docs] def to_hubo(self):
"""Construct a higher-order unconstrained binary optimization (HUBO)
problem from a binary polynomial.
Returns:
tuple: A 2-tuple of the form (`H`, `offset`) where `H` is the HUBO
and `offset` is the linear offset.
"""
if self.vartype is Vartype.SPIN:
return self.to_binary().to_hubo()
H = {tuple(term): bias for term, bias in self.items() if term}
offset = self[tuple()] if tuple() in self else 0
return H, offset
[docs] def to_binary(self, copy=False):
"""Return a binary polynomial over `{0, 1}` variables.
Args:
copy (optional, default=False):
If True, the returned polynomial is always a copy. Otherwise,
if the polynomial is binary-valued already it returns itself.
Returns:
:obj:`.BinaryPolynomial`
"""
if self.vartype is Vartype.BINARY:
if copy:
return self.copy()
else:
return self
new = BinaryPolynomial({}, Vartype.BINARY)
# s = 2x - 1
for term, bias in self.items():
for t in map(frozenset, powerset(term)):
newbias = bias * 2**len(t) * (-1)**(len(term) - len(t))
if t in new:
new[t] += newbias
else:
new[t] = newbias
return new
[docs] def to_spin(self, copy=False):
"""Return a binary polynomial over `{-1, +1}` variables.
Args:
copy (optional, default=False):
If True, the returned polynomial is always a copy. Otherwise,
if the polynomial is spin-valued already it returns itself.
Returns:
:obj:`.BinaryPolynomial`
"""
if self.vartype is Vartype.SPIN:
if copy:
return self.copy()
else:
return self
new = BinaryPolynomial({}, Vartype.SPIN)
# x = (s + 1) / 2
for term, bias in self.items():
newbias = bias / (2**len(term))
for t in map(frozenset, powerset(term)):
if t in new:
new[t] += newbias
else:
new[t] = newbias
return new
def powerset(iterable):
return itertools.chain.from_iterable(itertools.combinations(iterable, r)
for r in range(len(iterable)+1))