Defining Constraint Satisfaction Problems

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.