.. _constraints-definitions: ****************** Constraint catalog ****************** .. TODO : offset in the element constraint. 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: 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: :ref:`Sudoku ` .. _maximum: 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: :ref:`Frequency assignment ` .. _element: 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: :ref:`Sequencing jobs on a single machine ` .. _element2D: 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: :ref:`Paint Production ` .. _occurence: 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: :ref:`Sugar Production ` .. _gcc: 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: :ref:`Sugar Production ` .. _implies: 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: :ref:`Paint Production ` .. _equivalence: Equivalence =========== The ``KEquiv`` constructor allows the user to post an equivalence relation between two constraints. It takes two constraints as argument. Example: :ref:`Loaction of income tax offices ` .. _cycle: 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: :ref:`Paint Production 2 ` .. _binary_ac: 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 .. method:: 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: :ref:`Euler Knight tour ` .. _generalized_ac: 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 .. method:: 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: :ref:`Task assignment problem `