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
AllEqual	All arguments have the same value
Circuit	The sequence of variables form a circuit, 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'
Xor	The 'xor' exclusive-or constraint
Cumulative	Global cumulative constraint.
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].

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

All arguments have a different (distinct) value

decompose()

Returns the decomposition

deepcopy(memodict={})

get_bounds()

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

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

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

All nonzero arguments have a distinct value

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

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

All arguments have the same value

decompose()

Returns the decomposition

deepcopy(memodict={})

get_bounds()

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

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

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.

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.Cumulative(start, duration, end, demand, capacity)

Global cumulative constraint. Used for resource aware scheduling. Ensures no overlap between tasks and never exceeding the capacity of the resource Supports both varying demand across tasks or equal demand for all jobs

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

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.

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()

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.GlobalCardinalityCount(vars, vals, occ)

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].

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

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.

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.IfThenElse(condition, if_true, if_false)

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.InDomain(expr, arr)

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

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

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

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.Table(array, table)

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

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

class cpmpy.expressions.globalconstraints.Xor(arg_list)

The ‘xor’ exclusive-or constraint

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.

implies(other)

is_bool()

is it a Boolean (return type) Operator?

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

value()

cpmpy.expressions.globalconstraints.alldifferent(args)

cpmpy.expressions.globalconstraints.allequal(args)

cpmpy.expressions.globalconstraints.circuit(args)