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 namevars
:KIntVarArray
that represents the array containing the variables that must be differentalg
: optional argument that allows the user to specify the propagation algorithm used for evaluating the constraint. The default setting isKAllDifferent::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 namevar
:KIntVar
the variable that must be equal to the maximumvars
: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 targetValues
:KIntArray
the array storing the valuesIndex
:KIntVar
the variable storing the position of the targetoffset
: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 valuesI
:KIntVar
the variable storing the line at of the targetJ
:KIntVar
the variable storing the column at of the targetX
:KIntVar
the variable that must be equal to the targetI
:KIntVar
the variable storing the line at og the targetoffset1
:int
offset2
:int
name
: string that defines the constraint’s name
- class KElement2D¶
eltTerm2D
:KEltTerm2D
the value at the position (V,W) of an arrayX
:KIntVar
the variable that must be equal to the targetname
: 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 arrayv1
:KIntVar
orint
the value of the boundatLeast
:bool
true if the bound is a lower oneatMost
:bool
true if the bound is an upper one
- class Occurence¶
variables
:KIntVarArray
the array in which the occurences are countedtargets
:KIntArray
the list of values whose number of occurences are countedminOccur
:int
the lower bound for the occurencesmaxOccur
: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 namevars`: ``KIntVarArray
the array in which the occurences are countedvalues`: list of ``int
, the values whose occurences are countedlowerBound
: list ofint
the list of lower bounds for the occurencesupperBound
: list ofint
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 variablespreds
:KIntVarArray
that represents the array of predecessors variablesdist
:KIntVar
that represents the accumulated quantity variabledistmatrix
: 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 variablev2
:KIntVar
the second decision variablealg
: 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 variablev2
:KIntVar
the second decision variabletruthTable
:KTupleArray
representing the truth table of the constraintalg
: 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 variablesalg
: 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 algorithmname
: pretty name of the constraint- testIfSatisfied(values)¶
Return a boolean that asserts validity of tuple values
- class KGeneralizedArcConsistencyTableConstraint¶
vars
:KIntVarArray
the array of decision variablestruthTable
:KTupleArray
the truth table of the constraintalg
: 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 algorithmname
: pretty name of the constraint
Example: Task assignment problem