# Constraint catalog¶

This chapter contains a list of various constraints defined in the Artelys Kalis solver and explicits their implementation. The top of the list is composed of easy to use linear constraint. The end of the list shows how to create a new constraint type. Each constraint is briefly explained and, for a better understanding, a hyperlink to an example using the constraint can be found.

## All-different¶

The constraint all-different ensures that all the variables in a defined array take different values. It can be implemented using the `KAllDifferent` object.

class KAllDifferent
• `name`: string that defines the constraint’s name

• `vars`: `KIntVarArray` that represents the array containing the variables that must be different

• `alg`: optional argument that allows the user to specify the propagation algorithm used for evaluating the constraint. The default setting is `KAllDifferent::FORWARD_CHECKING`.

Example of use: Sudoku

## Maximum¶

The constraint maximum ensures that a variable is equal to the maximum of a list of variables. It can be implemented using the `KMax` object.

class KMax
• `name`: string that defines the constraint’s name

• `var`: `KIntVar` the variable that must be equal to the maximum

• `vars`: `KIntVarArray` that represents the array of variables which maximum should be derived.

Example: Frequency assignment

## Element¶

The constraint element ensures that a variable is equal to the value at the position V of an array, where V is also a variable. It can be implemented using the `KElement` object.

class KElement
• `X`: `KIntVar` the variable that must be equal to the target

• `Values`: `KIntArray` the array storing the values

• `Index`: `KIntVar` the variable storing the position of the target

• `offset`: `int`

• `name`: string that defines the constraint’s name

## Element 2D¶

The constraint element ensures that a variable is equal to the value at the position (V,W) of a matrix, where V and W are also variables. It can be implemented using the `KElement2D` object.

class KElement2D
• `lValues`: `KIntMatrix` the matrix storing the values

• `I`: `KIntVar` the variable storing the line at of the target

• `J`: `KIntVar` the variable storing the column at of the target

• `X`: `KIntVar` the variable that must be equal to the target

• `I`: `KIntVar` the variable storing the line at og the target

• `offset1`: `int`

• `offset2`: `int`

• `name`: string that defines the constraint’s name

class KElement2D
• `eltTerm2D`: `KEltTerm2D` the value at the position (V,W) of an array

• `X`: `KIntVar` the variable that must be equal to the target

• `name`: string that defines the constraint’s name

Example: Paint Production

## Occurence¶

The constraint occurence ensures that the number of occurences of a value in an array is between above (or below) a limit. It can be implemented using the `KOccurrence` object.

class Occurence
• `oc`: `KOccurTerm` the number of occurence of a value in an array

• `v1`: `KIntVar` or `int` the value of the bound

• `atLeast`: `bool` true if the bound is a lower one

• `atMost`: `bool` true if the bound is an upper one

class Occurence
• `variables`: `KIntVarArray` the array in which the occurences are counted

• `targets`: `KIntArray` the list of values whose number of occurences are counted

• `minOccur`: `int` the lower bound for the occurences

• `maxOccur`: `int` the upper bound for the occurences

Example: Sugar Production

## Global cardinality constraint¶

The constraint occurence can be posted for several values at once using the `KGlobalCardinalityConstraint` object.

class KGlobalCardinalityConstraint
• `name`: string that defines the constraint’s name

• `vars`: ``KIntVarArray` the array in which the occurences are counted

• `values`: list of ``int`, the values whose occurences are counted

• `lowerBound`: list of `int` the list of lower bounds for the occurences

• `upperBound`: list of `int` the list of upper bounds for the occurences

Example: Sugar Production

## Implies¶

The `KGuard` constructor allows the user to post an implication relation between two constraints.

It takes two constraints as argument, in the usual order for an implication.

Example: Paint Production

## Equivalence¶

The `KEquiv` constructor allows the user to post an equivalence relation between two constraints.

It takes two constraints as argument.

Example: Loaction of income tax offices

## Cycle¶

The cycle constraint ensures that the graph implicitly represented by a set of variables (= nodes) and their domains (= possible successors of a node) contains no sub-tours, that is, tours visiting only a subset of the nodes. It can be defined through the `KCycle` object.

class KCycle
• `vars`: `KIntVarArray` that represents the array of successors variables

• `preds`: `KIntVarArray` that represents the array of predecessors variables

• `dist`: `KIntVar` that represents the accumulated quantity variable

• `distmatrix`: a (nodes x nodes) `KIntMatrix` matrix of integers representing the quantity to add to the accumulated quantity variable when an edge (i,j) belongs to the tour.

Example: Paint Production 2

## Binary arc-consistency constraint¶

This constraint can be used to propagate a user-defined constraint over two variables (its propagation is based on the AC2001 algorithm). It is defined with the `KACBinConstraint` object or its table variant `KACBinTableConstraint` . Difference relies on the way the test function is used in the implementation of the constraint, and therefore the propagation algorithm behind. In the standard version of the Binary-ac constraint, end-user needs to create a derived class of `KACBinConstraint` which mainly overloads the `testIfSatisfied()` (constructor and copy-constructor are also needed). The former method is used by the propagation engine to test all valid combinations defined by the domain of variables. `testIfSatisfied()` is called each time one tuple needs to be validated.

class KACBinConstraint
• `v1`: `KIntVar` the first decision variable

• `v2`: `KIntVar` the second decision variable

• `alg`: allow user to set the propagation algorithm. ALGORITHM_AC2001 (default value) for propagation by the AC2001 algorithm , ALGORITHM_AC3 for propagation by the AC3 algorithm.

• `name`: pretty name of the constraint

testIfSatisfied(int val1, int val2)

Return a boolean that asserts validity of tuple (val1, val2)

class KACBinTableConstraint
• `v1`: `KIntVar` the first decision variable

• `v2`: `KIntVar` the second decision variable

• `truthTable`: `KTupleArray` representing the truth table of the constraint

• `alg`: allow user to set the propagation algorithm. ALGORITHM_AC2001 (default value) for propagation by the AC2001 algorithm , ALGORITHM_AC3 for propagation by the AC3 algorithm.

• `name`: pretty name of the constraint

Example: Euler Knight tour

## Generalized arc-consistency constraint¶

This constraint allows the user to define the valid support of the variables.

class KGeneralizedArcConsistencyConstraint
• `vars`: `KIntVarArray` the array of decision variables

• `alg`: allow user to set the propagation algorithm. GENERALIZED_ARC_CONSISTENCY (default value) for propagation by the generalized arc consistency algorithm, ARC_CONSISTENCY for propagation by the AC algorithm, FORWARD_CHECKING for propagation by the forward checking algorithm

• `name`: pretty name of the constraint

testIfSatisfied(values)

Return a boolean that asserts validity of tuple values

class KGeneralizedArcConsistencyTableConstraint
• `vars`: `KIntVarArray` the array of decision variables

• `truthTable`: `KTupleArray` the truth table of the constraint

• `alg`: allow user to set the propagation algorithm. GENERALIZED_ARC_CONSISTENCY (default value) for propagation by the generalized arc consistency algorithm, ARC_CONSISTENCY for propagation by the AC algorithm, FORWARD_CHECKING for propagation by the forward checking algorithm

• `name`: pretty name of the constraint