Source code for dwavebinarycsp.core.constraint

# Copyright 2018 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.
#
# ================================================================================================
"""
Solutions to a constraint satisfaction problem must satisfy certains conditions, the
constraints of the problem, such as equality and inequality constraints.
The :class:`Constraint` class defines constraints and provides functionality to
assist in constraint definition, such as verifying whether a candidate solution satisfies
a constraint.
"""
import itertools

from collections import Sized, Callable

import dimod

from dwavebinarycsp.exceptions import UnsatError

__all__ = ['Constraint']


[docs]class Constraint(Sized): """A constraint. Attributes: variables (tuple): Variables associated with the constraint. func (function): Function that returns True for configurations of variables that satisfy the constraint. Inputs to the function are ordered by :attr:`~Constraint.variables`. configurations (frozenset[tuple]): Valid configurations of the variables. Each configuration is a tuple of variable assignments ordered by :attr:`~Constraint.variables`. vartype (:class:`dimod.Vartype`): Variable type for the constraint. Accepted input values: * :attr:`~dimod.Vartype.SPIN`, ``'SPIN'``, ``{-1, 1}`` * :attr:`~dimod.Vartype.BINARY`, ``'BINARY'``, ``{0, 1}`` name (str): Name for the constraint. If not provided on construction, defaults to 'Constraint'. Examples: This example defines a constraint, named "plus1", based on a function that is True for :math:`(y1,y0) = (x1,x0)+1` on binary variables, and demonstrates some of the constraint's functionality. >>> def plus_one(y1, y0, x1, x0): # y=x++ for two bit binary numbers ... return (y1, y0, x1, x0) in [(0, 1, 0, 0), (1, 0, 0, 1), (1, 1, 1, 0)] ... >>> const = dwavebinarycsp.Constraint.from_func( ... plus_one, ... ['out1', 'out0', 'in1', 'in0'], ... dwavebinarycsp.BINARY, ... name='plus1') >>> print(const.name) # Check constraint defined as intended plus1 >>> len(const) 4 >>> in0, in1, out0, out1 = 0, 0, 1, 0 >>> const.func(out1, out0, in1, in0) # Order matches variables True This example defines a constraint based on specified valid configurations that represents an AND gate for spin variables, and demonstrates some of the constraint's functionality. >>> const = dwavebinarycsp.Constraint.from_configurations( ... [(-1, -1, -1), (-1, -1, 1), (-1, 1, -1), (1, 1, 1)], ... ['y', 'x1', 'x2'], ... dwavebinarycsp.SPIN) >>> print(const.name) # Check constraint defined as intended Constraint >>> isinstance(const, dwavebinarycsp.core.constraint.Constraint) True >>> (-1, 1, -1) in const.configurations # Order matches variables: y,x1,x2 True """ __slots__ = ('vartype', 'variables', 'configurations', 'func', 'name') # # Construction # @dimod.decorators.vartype_argument('vartype') def __init__(self, func, configurations, variables, vartype, name=None): self.vartype = vartype # checked by decorator if not isinstance(func, Callable): raise TypeError("expected input 'func' to be callable") self.func = func self.variables = variables = tuple(variables) num_variables = len(variables) if not isinstance(configurations, frozenset): configurations = frozenset(tuple(config) for config in configurations) # cast to tuples if len(configurations) == 0 and num_variables > 0: raise ValueError("constraint must have at least one feasible configuration") if not all(len(config) == num_variables for config in configurations): raise ValueError("all configurations should be of the same length") if len(vartype.value.union(*configurations)) >= 3: raise ValueError("configurations do not match vartype") self.configurations = configurations if name is None: name = 'Constraint' self.name = name
[docs] @classmethod @dimod.decorators.vartype_argument('vartype') def from_func(cls, func, variables, vartype, name=None): """Construct a constraint from a validation function. Args: func (function): Function that evaluates True when the variables satisfy the constraint. variables (iterable): Iterable of variable labels. vartype (:class:`~dimod.Vartype`/str/set): Variable type for the constraint. Accepted input values: * :attr:`~dimod.Vartype.SPIN`, ``'SPIN'``, ``{-1, 1}`` * :attr:`~dimod.Vartype.BINARY`, ``'BINARY'``, ``{0, 1}`` name (string, optional, default='Constraint'): Name for the constraint. Examples: This example creates a constraint that binary variables `a` and `b` are not equal. >>> import operator >>> const = dwavebinarycsp.Constraint.from_func(operator.ne, ['a', 'b'], 'BINARY') >>> print(const.name) Constraint >>> (0, 1) in const.configurations True This example creates a constraint that :math:`out = NOT(x)` for spin variables. >>> def not_(y, x): # y=NOT(x) for spin variables ... return (y == -x) ... >>> const = dwavebinarycsp.Constraint.from_func( ... not_, ... ['out', 'in'], ... {1, -1}, ... name='not_spin') >>> print(const.name) not_spin >>> (1, -1) in const.configurations True """ variables = tuple(variables) configurations = frozenset(config for config in itertools.product(vartype.value, repeat=len(variables)) if func(*config)) return cls(func, configurations, variables, vartype, name)
[docs] @classmethod def from_configurations(cls, configurations, variables, vartype, name=None): """Construct a constraint from valid configurations. Args: configurations (iterable[tuple]): Valid configurations of the variables. Each configuration is a tuple of variable assignments ordered by :attr:`~Constraint.variables`. variables (iterable): Iterable of variable labels. vartype (:class:`~dimod.Vartype`/str/set): Variable type for the constraint. Accepted input values: * :attr:`~dimod.Vartype.SPIN`, ``'SPIN'``, ``{-1, 1}`` * :attr:`~dimod.Vartype.BINARY`, ``'BINARY'``, ``{0, 1}`` name (string, optional, default='Constraint'): Name for the constraint. Examples: This example creates a constraint that variables `a` and `b` are not equal. >>> const = dwavebinarycsp.Constraint.from_configurations([(0, 1), (1, 0)], ... ['a', 'b'], dwavebinarycsp.BINARY) >>> print(const.name) Constraint >>> (0, 0) in const.configurations # Order matches variables: a,b False This example creates a constraint based on specified valid configurations that represents an OR gate for spin variables. >>> const = dwavebinarycsp.Constraint.from_configurations( ... [(-1, -1, -1), (1, -1, 1), (1, 1, -1), (1, 1, 1)], ... ['y', 'x1', 'x2'], ... dwavebinarycsp.SPIN, name='or_spin') >>> print(const.name) or_spin >>> (1, 1, -1) in const.configurations # Order matches variables: y,x1,x2 True """ def func(*args): return args in configurations return cls(func, configurations, variables, vartype, name)
# # Special Methods # def __len__(self): """The number of variables.""" return self.variables.__len__() def __repr__(self): return "Constraint.from_configurations({}, {}, {}, name='{}')".format(self.configurations, self.variables, self.vartype, self.name) def __eq__(self, constraint): return self.variables == constraint.variables and self.configurations == constraint.configurations def __ne__(self, constraint): return not self.__eq__(constraint) def __hash__(self): # uniquely defined by configurations/variables return hash((self.configurations, self.variables)) def __or__(self, const): if not isinstance(const, Constraint): raise TypeError("unsupported operand type(s) for |: 'Constraint' and '{}'".format(type(const).__name__)) if const and self and self.vartype is not const.vartype: raise ValueError("operand | only meaningful for Constraints with matching vartype") shared_variables = set(self.variables).intersection(const.variables) # dev note: if they share all variables, we could just act on the configurations if not shared_variables: # in this case we just append variables = self.variables + const.variables n = len(self) # need to know how to divide up the variables def union(*args): return self.func(*args[:n]) or const.func(*args[n:]) return self.from_func(union, variables, self.vartype, name='{} | {}'.format(self.name, const.name)) variables = self.variables + tuple(v for v in const.variables if v not in shared_variables) def union(*args): solution = dict(zip(variables, args)) return self.check(solution) or const.check(solution) return self.from_func(union, variables, self.vartype, name='{} | {}'.format(self.name, const.name)) def __and__(self, const): if not isinstance(const, Constraint): raise TypeError("unsupported operand type(s) for &: 'Constraint' and '{}'".format(type(const).__name__)) if const and self and self.vartype is not const.vartype: raise ValueError("operand & only meaningful for Constraints with matching vartype") shared_variables = set(self.variables).intersection(const.variables) # dev note: if they share all variables, we could just act on the configurations name = '{} & {}'.format(self.name, const.name) if not shared_variables: # in this case we just append variables = self.variables + const.variables n = len(self) # need to know how to divide up the variables def intersection(*args): return self.func(*args[:n]) and const.func(*args[n:]) return self.from_func(intersection, variables, self.vartype, name=name) variables = self.variables + tuple(v for v in const.variables if v not in shared_variables) def intersection(*args): solution = dict(zip(variables, args)) return self.check(solution) and const.check(solution) return self.from_func(intersection, variables, self.vartype, name=name) # # verification #
[docs] def check(self, solution): """Check that a solution satisfies the constraint. Args: solution (container): An assignment for the variables in the constraint. Returns: bool: True if the solution satisfies the constraint; otherwise False. Examples: This example creates a constraint that :math:`a \\ne b` on binary variables and tests it for two candidate solutions, with additional unconstrained variable c. >>> const = dwavebinarycsp.Constraint.from_configurations([(0, 1), (1, 0)], ... ['a', 'b'], dwavebinarycsp.BINARY) >>> solution = {'a': 1, 'b': 1, 'c': 0} >>> const.check(solution) False >>> solution = {'a': 1, 'b': 0, 'c': 0} >>> const.check(solution) True """ return self.func(*(solution[v] for v in self.variables))
# # transformation #
[docs] def fix_variable(self, v, value): """Fix the value of a variable and remove it from the constraint. Args: v (variable): Variable in the constraint to be set to a constant value. val (int): Value assigned to the variable. Values must match the :class:`.Vartype` of the constraint. Examples: This example creates a constraint that :math:`a \\ne b` on binary variables, fixes variable a to 0, and tests two candidate solutions. >>> const = dwavebinarycsp.Constraint.from_func(operator.ne, ... ['a', 'b'], dwavebinarycsp.BINARY) >>> const.fix_variable('a', 0) >>> const.check({'b': 1}) True >>> const.check({'b': 0}) False """ variables = self.variables try: idx = variables.index(v) except ValueError: raise ValueError("given variable {} is not part of the constraint".format(v)) if value not in self.vartype.value: raise ValueError("expected value to be in {}, received {} instead".format(self.vartype.value, value)) configurations = frozenset(config[:idx] + config[idx + 1:] # exclude the fixed var for config in self.configurations if config[idx] == value) if not configurations: raise UnsatError("fixing {} to {} makes this constraint unsatisfiable".format(v, value)) variables = variables[:idx] + variables[idx + 1:] self.configurations = configurations self.variables = variables def func(*args): return args in configurations self.func = func self.name = '{} ({} fixed to {})'.format(self.name, v, value)
[docs] def flip_variable(self, v): """Flip a variable in the constraint. Args: v (variable): Variable in the constraint to take the complementary value of its construction value. Examples: This example creates a constraint that :math:`a = b` on binary variables and flips variable a. >>> const = dwavebinarycsp.Constraint.from_func(operator.eq, ... ['a', 'b'], dwavebinarycsp.BINARY) >>> const.check({'a': 0, 'b': 0}) True >>> const.flip_variable('a') >>> const.check({'a': 1, 'b': 0}) True >>> const.check({'a': 0, 'b': 0}) False """ try: idx = self.variables.index(v) except ValueError: raise ValueError("variable {} is not a variable in constraint {}".format(v, self.name)) if self.vartype is dimod.BINARY: original_func = self.func def func(*args): new_args = list(args) new_args[idx] = 1 - new_args[idx] # negate v return original_func(*new_args) self.func = func self.configurations = frozenset(config[:idx] + (1 - config[idx],) + config[idx + 1:] for config in self.configurations) else: # SPIN original_func = self.func def func(*args): new_args = list(args) new_args[idx] = -new_args[idx] # negate v return original_func(*new_args) self.func = func self.configurations = frozenset(config[:idx] + (-config[idx],) + config[idx + 1:] for config in self.configurations) self.name = '{} ({} flipped)'.format(self.name, v)
# # copies and projections #
[docs] def copy(self): """Create a copy. Examples: This example copies constraint :math:`a \\ne b` and tests a solution on the copied constraint. >>> import operator >>> const = dwavebinarycsp.Constraint.from_func(operator.ne, ... ['a', 'b'], 'BINARY') >>> const2 = const.copy() >>> const2 is const False >>> const2.check({'a': 1, 'b': 1}) False """ # each object is itself immutable (except the function) return self.__class__(self.func, self.configurations, self.variables, self.vartype, name=self.name)
[docs] def projection(self, variables): """Create a new constraint that is the projection onto a subset of the variables. Args: variables (iterable): Subset of the constraint's variables. Returns: :obj:`.Constraint`: A new constraint over a subset of the variables. Examples: >>> const = dwavebinarycsp.Constraint.from_configurations([(0, 0), (0, 1)], ... ['a', 'b'], ... dwavebinarycsp.BINARY) >>> proj = const.projection(['a']) >>> proj.variables ('a',) >>> proj.configurations frozenset({(0,)}) """ # resolve iterables or mutability problems by casting the variables to a set variables = set(variables) if not variables.issubset(self.variables): raise ValueError("Cannot project to variables not in the constraint.") idxs = [i for i, v in enumerate(self.variables) if v in variables] configurations = frozenset(tuple(config[i] for i in idxs) for config in self.configurations) variables = tuple(self.variables[i] for i in idxs) return self.from_configurations(configurations, variables, self.vartype)