Constraint Satisfaction

Variables

Variables are derived from a common baseclass

class constrainingorder.variables.Variable(name, **kwargs)

Abstract baseclass for variables.

Variables describe the variables of a CSP. The instances are immutable and only make sense in connection with a Space.

description = None

description of the variable

discrete = None

whether the variable is discrete or continuous

domain = None

domain of the variable

name = None

name of the variable

Constrainingorder at the moment contains two types of Variables, DiscreteVariables and RealVariables

class constrainingorder.variables.DiscreteVariable(name, **kwargs)

Discrete variable with values from a DiscreteSet of elements.

__init__(name, **kwargs)

Create a new DiscreteVariable

Parameters:

• name (str) – The name of the variable
• description (str) – An optional description of the variable
• domain (DiscreteSet) – An optional domain for this variable, defaults to everything.

class constrainingorder.variables.RealVariable(name, **kwargs)

Continuous real variable with values from the real numbers.

__init__(name, **kwargs)

Create a new RealVariable

Parameters:

• name (str) – The name of the variable
• description (str) – An optional description of the variable
• domain (IntervalSet) – An optional domain for this variable, defaults to everything.

Constraints

Constraints are derived from a common baseclass

class constrainingorder.constraints.Constraint(domains)

consistent(lab)

check whether the labeling is consistent with this constraint

Parameters:lab (dict) – A dictionary with parameter names and values Return type:bool

domains = None

Domains imposed by node consistency for this constraint

satisfied(lab)

check whether the labeling satisfies this constraint

Parameters:lab (dict) – A dictionary with parameter names and values Return type:bool

vnames = None

Names of the variables affected by this constraint

Constrainingorder ships with a selection of constraints, but it is easy to add custom ones

class constrainingorder.constraints.FixedValue(variable, value)

Constraint that fixes a variable to a value

__init__(variable, value)

Create a new FixedValue constraint. It enforces that a variable takes on a particular, fixed value.

Parameters:

• variable (Variable) – Variable whose value is fixed
• value – Value to which it is fixed

Raises ValueError:  

if the value is not in the domain of the variable

class constrainingorder.constraints.AllDifferent(variables)

Constraint enforcing different values between a number of variables

__init__(variables)

Create a new AllDifferent constraint. It enforces that a set of variable takexs on different values.

Parameters:variables (sequence) – Variables for this Constraint

class constrainingorder.constraints.Domain(variable, domain)

Constraint that ensures that value of a variable falls into a given domain

__init__(variable, domain)

Create a new Domain constraint. It enforces that a variable takes on values from a specified set.

Parameters:

• variable (DiscreteVariable or RealVariable) – Variable whose value is restricted
• domain (DiscreteSet or IntervalSet) – Set of values to which variable is restricted

Binary relations are an important class of constraints. In Constraining Order they are derived from a common baseclass. New binary relations only need to implement the relation function. These relations can be used on Variables with values that offer the corresponding relations in the python data model.

class constrainingorder.constraints.BinaryRelation(var1, var2)

Abstract Base class for constraint the describe a binary relation between two variables.

__init__(var1, var2)

Create a new binary relation constraint between these two variables

Parameters:

• var1 (DiscreteVariable or RealVariable) – The first variable
• var2 (DiscreteVariable or RealVariable) – The second variable

relation(val1, val2)

evaluate the relation between two values

Parameters:

• val1 – The value of the first variable
• val2 – The value of the second variable

Return type:

bool

Constraining Order ships with the standard relations.

class constrainingorder.constraints.Equal(var1, var2)

Equality relation

class constrainingorder.constraints.NonEqual(var1, var2)

Inequality relation

class constrainingorder.constraints.Less(var1, var2)

Smaller-than relation

class constrainingorder.constraints.LessEqual(var1, var2)

Smaller or equal relation

class constrainingorder.constraints.Greater(var1, var2)

Larger-than relation

class constrainingorder.constraints.GreaterEqual(var1, var2)

Larger or equal relation

For DiscreteVariables, another way to represent relations is by the set of tuples that are fulfilling this relation. This is represented by the DiscreteBinaryRelation constraint

class constrainingorder.constraints.DiscreteBinaryRelation(var1, var2, tuples)

General binary relation between discrete variables represented by the tuples that are in this relation

__init__(var1, var2, tuples)

Create a new DiscreteBinaryRelation constraint. It restricts the values of the two variables to a set of possible combinations.

Parameters:

• var1 (DiscreteVariable or RealVariable) – The first variable
• var2 (DiscreteVariable or RealVariable) – The second variable
• tuples (sequence of tuples with values) – The allowed value combinations

Space

class constrainingorder.Space(variables, constraints)

A space is a description of the computation space for a specific CSP.

__init__(variables, constraints)

Create a new Space for a CSP

Parameters:

• variables (sequence of Variables) – The variables of the CSP
• constraints (sequence of Constraints) – The constraints of the CSP

consistent(lab)

Check whether the labeling is consistent with all constraints

constraints = None

list of constraints

domains = None

dictionary of variable names to DiscreteSet/IntervalSet with admissible values

is_discrete()

Return whether this space is discrete

satisfied(lab)

Check whether the labeling satisfies all constraints

variables = None

dictionary of variable names to variable instances

Solvers

To obtain one or all solutions to a CSP, one needs to use a solver. Solvers operate on a space. For good performance it might be good to reduce the problem space first.

constrainingorder.solver.ac3(space)

AC-3 algorithm. This reduces the domains of the variables by propagating constraints to ensure arc consistency.

Parameters:space (Space) – The space to reduce

constrainingorder.solver.solve(space, method=u'backtrack', ordering=None)

Generator for all solutions.

Parameters:

• method (str) – the solution method to employ
• ordering (sequence of parameter names) – an optional parameter ordering

Methods:

“backtrack”:simple chronological backtracking “ac-lookahead”:full lookahead