Global Constraints (cpmpy.expressions.globalconstraints)

Global constraints conveniently express non-primitive constraints.

Using global constraints

Solvers can have specialised implementations for global constraints. CPMpy has GlobalConstraint expressions so that they can be passed to the solver as is when supported.

If a solver does not support a global constraint (see solvers/) then it will be automatically decomposed by calling its .decompose() function. The .decompose() function returns two arguments:

• a list of simpler constraints replacing the global constraint

• if the decomposition introduces new variables, then the second argument has to be a list

  of constraints that (totally) define those new variables

As a user you should almost never subclass GlobalConstraint() unless you know of a solver that supports that specific global constraint, and that you will update its solver interface to support it.

For all other use cases, it sufficies to write your own helper function that immediately returns the decomposition, e.g.:

def alldifferent_except0(args):
    return [ ((var1!= 0) & (var2 != 0)).implies(var1 != var2) for var1, var2 in all_pairs(args)]

Numeric global constraints

CPMpy also implements __Numeric Global Constraints__. For these, the CPMpy GlobalConstraint does not exactly match what is implemented in the solver, but for good reason!!

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 constraint only captures 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 GlobalConstraint

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

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

    def decompose(self):
        return [self.args[0] != self.args[1]] # your decomposition

If it is a __numeric global constraint__ meaning that its return type is numeric (see Minimum and Element) then set is_bool=False in the super() constructor and preferably implement .value() accordingly.

Alternative decompositions

For advanced use cases where you want to use another decomposition than the standard decomposition of a GlobalConstraint expression, you can overwrite the ‘decompose’ function of the class, e.g.:

def my_circuit_decomp(self):
    return [self.args[0] == 1], [] # does not actually enforce circuit
circuit.decompose = my_circuit_decomp # attach it, no brackets!

vars = intvar(1,9, shape=10)
constr = circuit(vars)

Model(constr).solve()

The above will use ‘my_circuit_decomp’, if the solver does not natively support ‘circuit’.

List of classes

AllDifferent	All arguments have a different (distinct) value
AllDifferentExcept0	All nonzero arguments have a distinct value
AllDifferentExceptN	All arguments except those equal to a value in n have a distinct value.
AllEqual	All arguments have the same value
AllEqualExceptN	All arguments except those equal to a value in n have the same value.
Circuit	The sequence of variables form a circuit, where x[i] = j means that j is the successor of i.
SubCircuit	The sequence of variables form a subcircuit, where x[i] = j means that j is the successor of i.
SubCircuitWithStart	The sequence of variables form a subcircuit, where x[i] = j means that j is the successor of i.
Inverse	Inverse (aka channeling / assignment) constraint.
Table	The values of the variables in 'array' correspond to a row in 'table'
NegativeTable	The values of the variables in 'array' do not correspond to any row in 'table'
Xor	The 'xor' exclusive-or constraint
Cumulative	Global cumulative constraint.
IfThenElse
GlobalCardinalityCount	GlobalCardinalityCount(vars,vals,occ): The number of occurrences of each value vals[i] in the list of variables vars must be equal to occ[i].
DirectConstraint	A DirectConstraint will directly call a function of the underlying solver when added to a CPMpy solver
InDomain	The "InDomain" constraint, defining non-interval domains for an expression
Increasing	The "Increasing" constraint, the expressions will have increasing (not strictly) values
Decreasing	The "Decreasing" constraint, the expressions will have decreasing (not strictly) values
IncreasingStrict	The "IncreasingStrict" constraint, the expressions will have increasing (strictly) values
DecreasingStrict	The "DecreasingStrict" constraint, the expressions will have decreasing (strictly) values

class cpmpy.expressions.globalconstraints.AllDifferent(*args)

All arguments have a different (distinct) value

property args

decompose()

Returns the decomposition

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.AllDifferentExcept0(*arr)

All nonzero arguments have a distinct value

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.AllDifferentExceptN(arr, n)

All arguments except those equal to a value in n have a distinct value.

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.AllEqual(*args)

All arguments have the same value

property args

decompose()

Returns the decomposition

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.AllEqualExceptN(arr, n)

All arguments except those equal to a value in n have the same value.

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Circuit(*args)

The sequence of variables form a circuit, where x[i] = j means that j is the successor of i.

property args

decompose()

Decomposition for Circuit

Not sure where we got it from, MiniZinc has slightly different one: https://github.com/MiniZinc/libminizinc/blob/master/share/minizinc/std/fzn_circuit.mzn

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Cumulative(start, duration, end, demand, capacity)

Global cumulative constraint. Used for resource aware scheduling. Ensures that the capacity of the resource is never exceeded Equivalent to noOverlap when demand and capacity are equal to 1 Supports both varying demand across tasks or equal demand for all jobs

property args

decompose()

Time-resource decomposition from: Schutt, Andreas, et al. “Why cumulative decomposition is not as bad as it sounds.” International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2009.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Decreasing(*args)

The “Decreasing” constraint, the expressions will have decreasing (not strictly) values

property args

decompose()

Returns two lists of constraints:

1. the decomposition of the Decreasing constraint

2. empty list of defining constraints

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.DecreasingStrict(*args)

The “DecreasingStrict” constraint, the expressions will have decreasing (strictly) values

property args

decompose()

Returns two lists of constraints:

1. the decomposition of the DecreasingStrict constraint

2. empty list of defining constraints

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.DirectConstraint(name, arguments, novar=None)

A DirectConstraint will directly call a function of the underlying solver when added to a CPMpy solver

It can not be reified, it is not flattened, it can not contain other CPMpy expressions than variables. When added to a CPMpy solver, it will literally just directly call a function on the underlying solver, replacing CPMpy variables by solver variables along the way.

See the documentation of the solver (constructor) for details on how that solver handles them.

If you want/need to use what the solver returns (e.g. an identifier for use in other constraints), then use directvar() instead, or access the solver object from the solver interface directly.

property args

callSolver(CPMpy_solver, Native_solver)

Call the `directname`() function of the native solver, with stored arguments replacing CPMpy variables with solver variables as needed.

SolverInterfaces will call this function when this constraint is added.

Parameters:

• CPMpy_solver – a CPM_solver object, that has a solver_vars() function

• Native_solver – the python interface to some specific solver

Returns:

the response of the solver when calling the function

deepcopy(memodict={})

get_bounds()

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?

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.globalconstraints.GlobalCardinalityCount(vars, vals, occ, closed=False)

GlobalCardinalityCount(vars,vals,occ): The number of occurrences of each value vals[i] in the list of variables vars must be equal to occ[i].

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.GlobalConstraint(name, arg_list)

Abstract superclass of GlobalConstraints

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

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.IfThenElse(condition, if_true, if_false)

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.InDomain(expr, arr)

The “InDomain” constraint, defining non-interval domains for an expression

property args

decompose()

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 a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Increasing(*args)

The “Increasing” constraint, the expressions will have increasing (not strictly) values

property args

decompose()

Returns two lists of constraints:

1. the decomposition of the Increasing constraint

2. empty list of defining constraints

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.IncreasingStrict(*args)

The “IncreasingStrict” constraint, the expressions will have increasing (strictly) values

property args

decompose()

Returns two lists of constraints:

1. the decomposition of the IncreasingStrict constraint

2. empty list of defining constraints

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Inverse(fwd, rev)

Inverse (aka channeling / assignment) constraint. ‘fwd’ and ‘rev’ represent inverse functions; that is,

fwd[i] == x <==> rev[x] == i

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.LexChainLess(X)

Given a matrix X, LexChainLess enforces that all rows are lexicographically ordered.

property args

decompose()

Decompose to a series of LexLess constraints between subsequent rows

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.LexChainLessEq(X)

Given a matrix X, LexChainLessEq enforces that all rows are lexicographically ordered.

property args

decompose()

Decompose to a series of LexLessEq constraints between subsequent rows

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.LexLess(list1, list2)

Given lists X,Y, enforcing that X is lexicographically less than Y.

property args

decompose()

Implementation inspired by Hakan Kjellerstrand (http://hakank.org/cpmpy/cpmpy_hakank.py)

The decomposition creates auxiliary Boolean variables and constraints that collectively ensure X is lexicographically less than Y The auxiliary boolean vars are defined to represent if the given lists are lexicographically ordered (less or equal) up to the given index. Decomposition enforces through the constraining part that the first boolean variable needs to be true, and thus through the defining part it is enforced that if it is not strictly lexicographically less in a given index, then next index must be lexicographically less or equal. It needs to be strictly less in at least one index.

The use of auxiliary Boolean variables bvar ensures that the constraints propagate immediately, maintaining arc-consistency. Each bvar[i] enforces the lexicographic ordering at each position, ensuring that every value in the domain of X[i] can be extended to a consistent value in the domain of $Y_i$ for all subsequent positions.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.LexLessEq(list1, list2)

Given lists X,Y, enforcing that X is lexicographically less than Y (or equal).

property args

decompose()

Implementation inspired by Hakan Kjellerstrand (http://hakank.org/cpmpy/cpmpy_hakank.py)

The decomposition creates auxiliary Boolean variables and constraints that collectively ensure X is lexicographically less than Y The auxiliary boolean vars are defined to represent if the given lists are lexicographically ordered (less or equal) up to the given index. Decomposition enforces through the constraining part that the first boolean variable needs to be true, and thus through the defining part it is enforced that if it is not strictly lexicographically less in a given index, then next index must be lexicographically less or equal.

The use of auxiliary Boolean variables bvar ensures that the constraints propagate immediately, maintaining arc-consistency. Each bvar[i] enforces the lexicographic ordering at each position, ensuring that every value in the domain of X[i] can be extended to a consistent value in the domain of $Y_i$ for all subsequent positions.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.MDD(array, transitions)

MDD-constraint: an MDD (Multi-valued Decision Diagram) is an acyclic layerd graph starting from a single node and ending in one. Each edge layer corresponds to a variables and each path corresponds to a solution

The values of the variables in ‘array’ correspond to a path in the mdd formed by the transitions in ‘transitions’. Root node is the first node used as a start in the first transition (i.e. transitions[0][0])

spec:

• array: an array of CPMpy expressions (integer variable, global functions,…)

• transitions: an array of tuples (nodeID, int, nodeID) where nodeID is some unique identifiers for the nodes

(int or str are fine)

Example:

The following transitions depict a 3 layer MDD, starting at ‘r’ and ending in ‘t’ (“r”, 0, “n1”), (“r”, 1, “n2”), (“r”, 2, “n3”), (“n1”, 2, “n4”), (“n2”, 2, “n4”), (“n3”, 0, “n5”), (“n4”, 0, “t”), (“n5”, 1, “t”) Its graphical representation is:

r

0/ |1  X

n1 n2 n3 2| /2 /O Y

n4 n5

0 /1 Z

t

It has 3 paths, corresponding to 3 solution for (X,Y,Z): (0,2,0), (1,2,0) and (2,0,1)

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.NegativeTable(array, table)

The values of the variables in ‘array’ do not correspond to any row in ‘table’

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.NoOverlap(start, dur, end)

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Precedence(vars, precedence)

Constraint enforcing some values have precedence over others. Given an array of variables X and a list of precedences P: Then in order to satisfy the constraint, if X[i] = P[j+1], then there exists a X[i’] = P[j] with i’ < i

property args

decompose()

Decomposition based on: Law, Yat Chiu, and Jimmy HM Lee. “Global constraints for integer and set value precedence.” Principles and Practice of Constraint Programming–CP 2004: 10th International Conference, CP 2004

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Regular(array, transitions, start, ends)

Regular-constraint (or Automaton-constraint): An automaton is a directed graph. Each node correspond to a state. Each edge correspond to a transition from one state to the other given a value. A given node serves as start node. A path a size N is a solution if, by following the transitions given by the values of the variables we end up in one of the defined end nodes.

The values of the variables in ‘array’ correspond to a path in the automaton formed by the transitions in ‘transitions’. The path starts in ‘start’ and ends in one of the ending states (‘ends’)

spec:

• array: an array of CPMpy expressions (integer variable, global functions,…)

• transitions: an array of tuples (nodeID, int, nodeID) where nodeID is some unique identifiers for the nodes

(int or str) - start: a singular nodeID node start of the automaton - ends: a list of nodeID corresponding to the accepting end nodes

Example:

The following transitions depict an automaton, starting at ‘a’ and ending in [‘c’] (“a”, 1, “b”), (“b”, 1, “c”), (“b”, 0, “b”), (“c”, 1, “c”), (“c”, 0, “b”) Its graphical representation is:

|--0----| v |

a -1-> b -1-> c –

^ ^ |

|-0-| |-1-

It has 2 solution for (X,Y,Z): (1,1,1) and (1,0,1) It has 4 solutions for (W,X,Y,Z): (1,1,1,1), (1,1,0,1), (1,0,0,1) and (1,0,1,1)

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.SubCircuit(*args)

The sequence of variables form a subcircuit, where x[i] = j means that j is the successor of i. Contrary to Circuit, there is no requirement on all nodes needing to be part of the circuit. Nodes which aren’t part of the subcircuit, should self loop i.e. x[i] = i. The subcircuit can be empty (all stops self-loop). A length 1 subcircuit is treated as an empty subcircuit.

Global Constraint Catalog: https://sofdem.github.io/gccat/gccat/Cproper_circuit.html

property args

decompose()

Decomposition for SubCircuit

A mix of the above Circuit decomposition, with elements from the Minizinc implementation for the support of optional visits: https://github.com/MiniZinc/minizinc-old/blob/master/lib/minizinc/std/subcircuit.mzn

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.SubCircuitWithStart(*args, start_index: int = 0)

The sequence of variables form a subcircuit, where x[i] = j means that j is the successor of i. Contrary to Circuit, there is no requirement on all nodes needing to be part of the circuit. Nodes which aren’t part of the subcircuit, should self loop i.e. x[i] = i. The size of the subcircuit should be strictly greater than 1, so not all stops can self loop (as otherwise the start_index will never get visited). start_index will be treated as the start of the subcircuit. The only impact of start_index is that it will be guaranteed to be inside the subcircuit.

Global Constraint Catalog: https://sofdem.github.io/gccat/gccat/Cproper_circuit.html

property args

decompose()

Decomposition for SubCircuitWithStart.

SubCircuitWithStart simply gets decomposed into SubCircuit and a constraint enforcing the start_index to be part of the subcircuit.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Table(array, table)

The values of the variables in ‘array’ correspond to a row in ‘table’

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.Xor(arg_list)

The ‘xor’ exclusive-or constraint

property args

decompose()

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.

To ensure equivalence of decomposition, we split into contraining and defining constraints. Defining constraints (totally) define new auxiliary variables needed for the decomposition, they can always be enforced top-level.

deepcopy(memodict={})

get_bounds()

Returns the bounds of a Boolean global constraint. Numerical global constraints should reimplement this.

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?

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.globalconstraints.alldifferent(args)

cpmpy.expressions.globalconstraints.allequal(args)

cpmpy.expressions.globalconstraints.circuit(args)