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

Example: Sequencing jobs on a single machine

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

Example: Task assignment problem