Global Functions (cpmpy.expressions.globalfunctions)

Global functions conveniently express numerical global constraints.

Using global functions

If a solver does not support such a global function (see solvers/), then it will be automatically decomposed by calling its .decompose_comparison() function.

CPMpy GlobalFunctions does not exactly match what is implemented in the solvers. Solvers can have specialised implementations for global functions, when used in a comparison, as global constraints. These global functions will be treated as global constraints in such cases.

For example solvers may implement the global constraint Minimum(iv1, iv2, iv3) == iv4 through an API call addMinimumEquals([iv1,iv2,iv3], iv4).

However, CPMpy also wishes to support the expressions Minimum(iv1, iv2, iv3) > iv4 as well as iv4 + Minimum(iv1, iv2, iv3).

Hence, the CPMpy global functions only capture the Minimum(iv1, iv2, iv3) part, whose return type is numeric and can be used in any other CPMpy expression. Only at the time of transforming the CPMpy model to the solver API, will the expressions be decomposed and auxiliary variables introduced as needed such that the solver only receives Minimum(iv1, iv2, iv3) == ivX expressions. This is the burden of the CPMpy framework, not of the user who wants to express a problem formulation.

Subclassing GlobalFunction

If you do wish to add a GlobalFunction, because it is supported by solvers or because you will do advanced analysis and rewriting on it, then preferably define it with a standard comparison decomposition, e.g.:

class my_global(GlobalFunction):
    def __init__(self, args):
        super().__init__("my_global", args)

    def decompose_comparison(self):
        return [self.args[0] + self.args[1]] # your decomposition

Also, implement .value() accordingly.

List of classes

Minimum	Computes the minimum value of the arguments
Maximum	Computes the maximum value of the arguments
Abs	Computes the absolute value of the argument
Element	The 'Element' global constraint enforces that the result equals Arr[Idx] with 'Arr' an array of constants or variables (the first argument) and 'Idx' an integer decision variable, representing the index into the array.
Count	The Count (numerical) global constraint represents the number of occurrences of val in arr
Among	The Among (numerical) global constraint represents the number of variable that take values among the values in arr
NValue	The NValue constraint counts the number of distinct values in a given set of variables.
NValueExcept	The NValueExceptN constraint counts the number of distinct values,

class cpmpy.expressions.globalfunctions.Abs(expr)

Computes the absolute value of the argument

property args

decompose_comparison(cpm_op, cpm_rhs)

Decomposition if it’s part of a comparison

Returns two lists of constraints:

1. constraints representing the comparison

2. constraints that (totally) define new auxiliary variables needed in the decomposition, they should be enforced toplevel.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.Among(arr, vals)

The Among (numerical) global constraint represents the number of variable that take values among the values in arr

property args

decompose_comparison(cmp_op, cmp_rhs)

Among(arr, vals) can only be decomposed if it’s part of a comparison’

deepcopy(memodict={})

get_bounds()

Returns the bounds of the global function

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.Count(arr, val)

The Count (numerical) global constraint represents the number of occurrences of val in arr

property args

decompose_comparison(cmp_op, cmp_rhs)

Count(arr,val) can only be decomposed if it’s part of a comparison

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.Element(arr, idx)

The ‘Element’ global constraint enforces that the result equals Arr[Idx] with ‘Arr’ an array of constants or variables (the first argument) and ‘Idx’ an integer decision variable, representing the index into the array.

Solvers implement it as Arr[Idx] == Y, but CPMpy will automatically derive or create an appropriate Y. Hence, you can write expressions like Arr[Idx] + 3 <= Y

Element is a CPMpy built-in global constraint, so the class implements a few more extra things for convenience (.value() and .__repr__()). It is also an example of a ‘numeric’ global constraint.

property args

decompose_comparison(cpm_op, cpm_rhs)

Element(arr,ix) represents the array lookup itself (a numeric variable) When used in a comparison relation: Element(arr,idx) <CMP_OP> CMP_RHS it is a constraint, and that one can be decomposed.

Returns two lists of constraints:

1. constraints representing the comparison

2. constraints that (totally) define new auxiliary variables needed in the decomposition, they should be enforced toplevel.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.GlobalFunction(name, arg_list)

Abstract superclass of GlobalFunction

Like all expressions it has a .name and .args property. Overwrites the .is_bool() method.

property args

decompose_comparison(cmp_op, cmp_rhs)

Returns a decomposition into smaller constraints.

The decomposition might create auxiliary variables and use other global constraints as long as it does not create a circular dependency.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the global function

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.Maximum(arg_list)

Computes the maximum value of the arguments

property args

decompose_comparison(cpm_op, cpm_rhs)

Decomposition if it’s part of a comparison

Returns two lists of constraints:

1. constraints representing the comparison

2. constraints that (totally) define new auxiliary variables needed in the decomposition, they should be enforced toplevel.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.Minimum(arg_list)

Computes the minimum value of the arguments

property args

decompose_comparison(cpm_op, cpm_rhs)

Decomposition if it’s part of a comparison

Returns two lists of constraints:

1. constraints representing the comparison

2. constraints that (totally) define new auxiliary variables needed in the decomposition, they should be enforced toplevel.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.NValue(arr)

The NValue constraint counts the number of distinct values in a given set of variables.

property args

decompose_comparison(cmp_op, cpm_rhs)

NValue(arr) can only be decomposed if it’s part of a comparison

Based on “simple decomposition” from:

Bessiere, Christian, et al. “Decomposition of the NValue constraint.” International Conference on Principles and Practice of Constraint Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

class cpmpy.expressions.globalfunctions.NValueExcept(arr, n)

The NValueExceptN constraint counts the number of distinct values,

not including value N, if any argument is assigned to it.

property args

decompose_comparison(cmp_op, cpm_rhs)

NValue(arr) can only be decomposed if it’s part of a comparison

Based on “simple decomposition” from:

Bessiere, Christian, et al. “Decomposition of the NValue constraint.” International Conference on Principles and Practice of Constraint Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.

deepcopy(memodict={})

get_bounds()

Returns the bounds of the (numerical) global constraint

has_subexpr()

Does it contains nested Expressions (anything other than a _NumVarImpl or a constant)? Is of importance when deciding whether certain transformations are needed along particular paths of the expression tree. Results are cached for future calls and reset when the expression changes (in-place argument update).

implies(other)

is_bool()

is it a Boolean (return type) Operator? No

is_total()

Returns whether it is a total function. If true, its value is defined for all arguments

set_description(txt, override_print=True, full_print=False)

update_args(args)

Allows in-place update of the expression’s arguments. Resets all cached computations which depend on the expression tree.

value()

cpmpy.expressions.globalfunctions.element(arg_list)