Defining Constraints

Solutions to a constraint satisfaction problem must satisfy certains conditions, the constraints of the problem, such as equality and inequality constraints. The Constraint class defines constraints and provides functionality to assist in constraint definition, such as verifying whether a candidate solution satisfies a constraint.

Class

class Constraint(func, configurations, variables, vartype, name=None)[source]

A constraint.

variables

Variables associated with the constraint.

Type:tuple
func

Function that returns True for configurations of variables that satisfy the constraint. Inputs to the function are ordered by variables.

Type:function
configurations

Valid configurations of the variables. Each configuration is a tuple of variable assignments ordered by variables.

Type:frozenset[tuple]
vartype

Variable type for the constraint. Accepted input values:

Type:dimod.Vartype
name

Name for the constraint. If not provided on construction, defaults to ‘Constraint’.

Type:str

Examples

This example defines a constraint, named “plus1”, based on a function that is True for \((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

Methods

Construction

Constraint.from_configurations(…[, name]) Construct a constraint from valid configurations.
Constraint.from_func(func, variables, vartype) Construct a constraint from a validation function.

Satisfiability

Constraint.check(solution) Check that a solution satisfies the constraint.

Transformations

Constraint.fix_variable(v, value) Fix the value of a variable and remove it from the constraint.
Constraint.flip_variable(v) Flip a variable in the constraint.

Copies and projections

Constraint.copy() Create a copy.
Constraint.projection(variables) Create a new constraint that is the projection onto a subset of the variables.