Defining Constraint Satisfaction Problems

Deprecated since version 0.3.1: dwavebinarycsp is deprecated and will be removed in Ocean 10. For solving problems with constraints, we recommand using the hybrid solvers in the Leap service. You can find documentation for the hybrid solvers at Hybrid Solvers.

Constraint satisfaction problems require that all a problem’s variables be assigned values, out of a finite domain, that result in the satisfying of all constraints. The ConstraintSatisfactionProblem class aggregates all constraints and variables defined for a problem and provides functionality to assist in problem solution, such as verifying whether a candidate solution satisfies the constraints.

Class

class ConstraintSatisfactionProblem(vartype)

A constraint satisfaction problem.

Parameters:

vartype (Vartype/str/set) –

Variable type for the binary quadratic model. Supported values are:

• SPIN, 'SPIN', {-1, 1}

• BINARY, 'BINARY', {0, 1}

constraints

Constraints that together constitute the constraint satisfaction problem. Valid solutions satisfy all of the constraints.

Type:

list[Constraint]

variables

Variables of the constraint satisfaction problem as a dict, where keys are the variables and values a list of all of constraints associated with the variable.

Type:

dict[variable, list[Constraint]]

vartype

Enumeration of valid variable types. Supported values are SPIN or BINARY. If vartype is SPIN, variables can be assigned -1 or 1; if BINARY, variables can be assigned 0 or 1.

Type:

dimod.Vartype

Example

This example creates a binary-valued constraint satisfaction problem, adds two constraints, \(a = b\) and \(b \ne c\), and tests \(a,b,c = 1,1,0\).

>>> import operator
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem('BINARY')
>>> csp.add_constraint(operator.eq, ['a', 'b'])
>>> csp.add_constraint(operator.ne, ['b', 'c'])
>>> csp.check({'a': 1, 'b': 1, 'c': 0})
True

Methods

Adding variables and constraints

ConstraintSatisfactionProblem.add_constraint(...)	Add a constraint.
ConstraintSatisfactionProblem.add_variable(v)	Add a variable.

Satisfiability

ConstraintSatisfactionProblem.check(solution)

Check that a solution satisfies all of the constraints.

Transformations

ConstraintSatisfactionProblem.fix_variable(v, ...)

Fix the value of a variable and remove it from the constraint satisfaction problem.