4.5.1. Prolog facts describing a constraint

For each global constraint, the electronic version of its description is provided as a Prolog file (see the link “.pl file” at the beginning of the section corresponding to a global constraint). In addition the file “eval.pl” contains a set of shared utilities used for evaluating the constraints. This electronic version was used for generating the LaTeX file of this catalogue, the figures associated with the graph-based description and a filtering algorithm for some of the constraints that use the automaton-based description. Within the electronic version, each constraint is described in terms of meta-data. A typical entry is:

ctr_date(minimum, ['20000128','20030820','20040530',

                   '20041230','20060811','20090416']).

ctr_origin(minimum, '\\index{CHIP|indexuse}CHIP', []).

ctr_arguments(minimum, ['MIN'-dvar, 'VARIABLES'-collection(var-dvar)]).

ctr_exchangeable(minimum,

                 [items('VARIABLES',all),

                  vals(['VARIABLES'^var],int,=\=,all,in),

                  translate(['MIN','VARIABLES'^var])]).

ctr_synonyms(minimum, [min]).

ctr_restrictions(minimum, [size('VARIABLES')>0, required('VARIABLES',var)]).

ctr_typical(minimum, [size('VARIABLES') > 1, range('VARIABLES'^var) > 1]).

ctr_pure_functional_dependency(minimum, []).

ctr_functional_dependency(minimum, 1, [2]).

ctr_aggregate(minimum, [], [min, union]).

ctr_graph(minimum,

          ['VARIABLES'],

          2,

          ['CLIQUE'>>collection(variables1,variables2)],

          [variables1^key=variables2^key #\/ variables1^var<variables2^var],

          ['ORDER'(0,'MAXINT',var)='MIN'],

          []).

ctr_example(minimum,

            [minimum(2,[[var-3],[var-2],[var-7],[var-2],[var-6]]),

             minimum(7,[[var-8],[var-8],[var-7],[var-8],[var-7]])]).

ctr_cond_imply(minimum, deepest_valley,

               [first('VARIABLES'^var) > 'MIN',

                last('VARIABLES'^var) > 'MIN'], [], id).

ctr_see_also(minimum,

 [link('generalisation', minimum_modulo,

       '%e replaced by %e', [variable, variable mod constant]),

  link('specialisation', min_n,

       'minimum or order %e replaced by absolute minimum', [n]),

  link('comparison swapped', maximum, '', []),

  link('common keyword', maximum, '%k', ['order constraint']),

  link('soft variant', open_minimum, '%k', ['open constraint']),

  link('soft variant', minimum_except_0, 'value %e is ignored', [0]),

  link('implies', between_min_max, '', []),

  link('implies', in, '', []),

  link('implied by', and, '', [])]).

ctr_key_words(minimum,['order constraint'                        ,

                       'minimum'                                 ,

                       'maxint'                                  ,

                       'automaton'                               ,

                       'automaton without counters'              ,

                       'reified automaton constraint'            ,

                       'centered cyclic(1) constraint network(1)',

                       'arc-consistency'                         ]).

ctr_persons(minimum,['Beldiceanu N.']).

ctr_eval(minimum, [builtin(minimum_b), automaton(minimum_a)]).

minimum_b(MIN, VARIABLES) :-

    check_type(dvar, MIN),      collection(VARIABLES, [dvar]),

    length(VARIABLES, N),       N > 0,

    get_attr1(VARIABLES, VARS), minimum(MIN, VARS).

minimum_a(MIN, VARIABLES) :-   % 0: MIN<VAR, 1: MIN=VAR, 2: MIN>VAR

    minimum_signature(VARIABLES, SIGNATURE, MIN),

    automaton(SIGNATURE, _, SIGNATURE,

              [source(s),sink(t)],

              [arc(s,0,s),arc(s,1,t),arc(t,1,t),arc(t,0,t)],

              [],[],[]).

minimum_signature([], [], _).

minimum_signature([[var-VAR]|VARs], [S|Ss], MIN) :-

    S in 0..2,

    MIN #< VAR #<=> S #= 0, MIN #= VAR #<=> S #= 1, MIN #> VAR #<=> S #= 2,

    minimum_signature(VARs, Ss, MIN).

ctr_sol(minimum,2,0,2,9,[0-5,1-3,2-1]).

ctr_sol(minimum,3,0,3,64,[0-37,1-19,2-7,3-1]).

ctr_sol(minimum,4,0,4,625,[0-369,1-175,2-65,3-15,4-1]).

ctr_sol(minimum,5,0,5,7776,[0-4651,1-2101,2-781,3-211,4-31,5-1]).

ctr_sol(minimum,6,0,6,117649,[0-70993,1-31031,2-11529,3-3367,

                              4-665,5-63,6-1]).

ctr_sol(minimum,7,0,7,2097152,[0-1273609,1-543607,2-201811,3-61741,

                               4-14197,5-2059,6-127,7-1]).

ctr_sol(minimum,8,0,8,43046721,[0-26269505,1-11012415,2-4085185,

                                3-1288991,4-325089,5-58975,6-6305,7-255,

                                8-1]).

and consists of the following Prolog facts, where $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴}$ is the name of the constraint under consideration. The facts are organised in the following 20 items:

• Items 1, 2, 3, 4, 16 and 17 provide general information about a global constraint,

• Items 5, 6, 7 and 8 describe the arguments of a global constraint.

• Items 9 and 10 give properties of the arguments of a global constraint, e.g. functional dependency, contractibility.

• Item 11 describes symmetries of a global constraint, i.e. list of mappings (e.g., permutation of arguments) that preserve the solutions of a global constraint.

• Items 12 and 13 describes the meaning of a global constraint in terms of a graph-based representation.

• Item 14 provides one or several ground instances which hold.

• Item 18 gives the list of available evaluators of a global constraint.

• Item 19 provides the number of solutions of the constraint under various assumptions on the number of variables and on their initial domains.

• Item 20 describes the meaning of a global constraint in terms of a set of first order logic formulae.

Items 1, 2, 6 and 14 are mandatory, while all other items are optional. We now give the different items:

1. ctr_date$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙳𝙰𝚃𝙴𝚂}\_\mathrm{𝙾𝙵}\_\mathrm{𝙼𝙾𝙳𝙸𝙵𝙸𝙲𝙰𝚃𝙸𝙾𝙽𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙳𝙰𝚃𝙴𝚂}\_\mathrm{𝙾𝙵}\_\mathrm{𝙼𝙾𝙳𝙸𝙵𝙸𝙲𝙰𝚃𝙸𝙾𝙽𝚂}$ is a list of dates when the description of the constraint was modified.

2. ctr_origin$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂}\_\mathrm{𝙽𝙰𝙼𝙴𝚂})$

   • $\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶}$ is a string denoting the origin of the constraint. $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂}\_\mathrm{𝙽𝙰𝙼𝙴𝚂}$ is a possibly empty list of constraint names related to the origin of the constraint.

3. ctr_usual_name$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝚄𝚂𝚄𝙰𝙻}\_\mathrm{𝙽𝙰𝙼𝙴})$

   • When, for some reason, the constraint name used in the catalogue does not correspond to the usual name of the constraint, $\mathrm{𝚄𝚂𝚄𝙰𝙻}\_\mathrm{𝙽𝙰𝙼𝙴}$ provides the usual name of the constraint. This stems from the fact that each entry of the catalogue should have a distinct name. This is for instance the case for the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚙𝚊𝚝𝚑}$ and the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}\_\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraints which are both usually called $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$.

4. ctr_synonyms$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚂𝚈𝙽𝙾𝙽𝚈𝙼𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚂𝚈𝙽𝙾𝙽𝚈𝙼𝚂}$ is a list of synonyms for the constraint. This stems from the fact that, quite often, different authors use a different name for the same constraint. This is for instance the case for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the $\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints.

5. ctr_types$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚃𝚈𝙿𝙴𝚂}\_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚃𝚈𝙿𝙴𝚂}\_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂}$ is a list of elements of the form $\mathrm{𝚗𝚊𝚖𝚎}$-$\mathrm{𝚝𝚢𝚙𝚎}$, where $\mathrm{𝚗𝚊𝚖𝚎}$ is the name of a new type and $\mathrm{𝚝𝚢𝚙𝚎}$ the type itself (usually a collection). Basic and compound data types were respectively introduced in sections 2.2.1 and 2.2.2 on page 2.2.1. This field is only used when we need to declare a new type that will be used for specifying the type of the arguments of the constraint. This is for instance the case when one argument of the constraint is a collection for which the type of one attribute is also a collection. This is for instance the case for the $\mathrm{𝚍𝚒𝚏𝚏𝚗}$ constraint where the unique argument $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂}$ is a collection of $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴}$; $\mathrm{𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴}$ refers to a new type declared in $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚃𝚈𝙿𝙴𝚂}\_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂}$.

6. ctr_arguments$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙰𝚁𝙶𝚄𝙼𝙴𝙽𝚃𝚂}\_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙰𝚁𝙶𝚄𝙼𝙴𝙽𝚃𝚂}\_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂}$ is a list of elements of the form $\mathrm{𝚊𝚛𝚐}$-$\mathrm{𝚝𝚢𝚙𝚎}$, where $\mathrm{𝚊𝚛𝚐}$ is the name of an argument of the constraint and $\mathrm{𝚝𝚢𝚙𝚎}$ the type of the argument. Basic and compound data types were respectively introduced in sections 2.2.1 and 2.2.2 on page 2.2.1.

7. ctr_restrictions$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}$ is a list of restrictions on the different arguments of the constraint. Possible restrictions were described in Section 2.2.3 on page 2.2.3.

8. ctr_typical$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂})$

   • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}$ is a list of typical restrictions on the different arguments of the constraint, i.e. even though these restrictions are not mandatory they usually hold. Possible restrictions were described in Section 2.2.3 on page 2.2.3.

9. ctr_pure_functional_dependency$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂})$

   • Indicate that, under the assumption that all restrictions described by $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}$ hold, at least one of the arguments of the constraint is functionally determined by the other arguments. Possible restrictions were described in Section 2.2.3 on page 2.2.3. Which argument $\mathrm{𝙰𝚁𝙶}$ is determined by which subset of arguments $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙰𝚁𝙶𝚂}$ is described by the fact ctr_functional_dependency$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},$ $\mathrm{𝙰𝚁𝙶},$ $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙰𝚁𝙶𝚂})$ where arguments are denoted by their positions within the constraint.

10. ctr_aggregate$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂},\mathrm{𝙰𝚁𝙶}\_\mathrm{𝙰𝙶𝙶𝚁𝙴𝙶𝙰𝚃𝙸𝙾𝙽})$

    Denotes that, given two instances of the constraint that both satisfy all restrictions described by $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}$, we can combine (i.e., aggregate) these two instances in order to obtain an implied constraint, which has the same name as the first two constraints. We use $\mathrm{𝙰𝚁𝙶}\_\mathrm{𝙰𝙶𝙶𝚁𝙴𝙶𝙰𝚃𝙸𝙾𝙽}$ in order to obtain the arguments of the implied constraint as described in the keyword Aggregate.

11. ctr_exchangeable$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙴𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙴𝚂}$ is a list of mappings preserving the solutions to the constraint. Possible mappings were described in Section 2.2.5 on page 2.2.5.

12. ctr_derived_collections$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙳𝙴𝚁𝙸𝚅𝙴𝙳}\_\mathrm{𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙳𝙴𝚁𝙸𝚅𝙴𝙳}\_\mathrm{𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂}$ is a list of derived collections. Derived collections are collections that are computed from the arguments of the constraint and are used in the graph-based description. Derived collections were described in Section 2.3.2.1 on page 2.3.2.1.

13. ctr_graph$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙸𝙽𝙿𝚄𝚃},\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙰𝚁𝙸𝚃𝚈},$

                 $\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙾𝚁𝚂},\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂},\mathrm{𝙶𝚁𝙰𝙿𝙷}\_\mathrm{𝙿𝚁𝙾𝙿𝙴𝚁𝚃𝙸𝙴𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙸𝙽𝙿𝚄𝚃}$ is a list of collections used for creating the vertices of the initial graph. This was described at page 2.3.3.1 of Section 2.3.3.1.

    • $\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙰𝚁𝙸𝚃𝚈}$ is the number of vertices of an arc. Arc arity was explained at page 2.3.3.1 of Section 2.3.3.1.

    • $\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙾𝚁𝚂}$ is a list of arc generators. Arc generators were introduced at page 2.3.3.1 of Section 2.3.3.1.

    • $\mathrm{𝙰𝚁𝙲}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂}$ is a list of arc constraints. Arc constraints were defined in Section 2.3.2.2 on page 2.3.2.2.

    • $\mathrm{𝙶𝚁𝙰𝙿𝙷}\_\mathrm{𝙿𝚁𝙾𝙿𝙴𝚁𝚃𝙸𝙴𝚂}$ is a list of graph properties. Graph properties were described in Section 2.3.2.4 on page 2.3.2.4.

14. ctr_example$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙴𝚇𝙰𝙼𝙿𝙻𝙴𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙴𝚇𝙰𝙼𝙿𝙻𝙴𝚂}$ is a list of examples (usually one). Each example corresponds to a ground instance for which the constraint holds.

15. ctr_cond_imply$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃},$

                      $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}\_\mathrm{𝙲𝚃𝚁},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}\_\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝚃𝚁},\mathrm{𝙼𝙰𝚃𝙲𝙷𝙸𝙽𝙶})$

    $\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$ is a constraint implied by $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴}$ provided that

    • the list of restrictions $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}\_\mathrm{𝙲𝚃𝚁}$ holds for the constraint $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴}$, and

    • the list of restrictions $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂}\_\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝚃𝚁}$ holds for the constraint $\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$.

    $\mathrm{𝙼𝙰𝚃𝙲𝙷𝙸𝙽𝙶}$ describes how to create the arguments of $\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$ from the arguments of $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴}$. Note that some arguments of $\mathrm{𝙸𝙼𝙿𝙻𝙸𝙴𝙳}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$ may not be explicitly mentioned since they correspond to existentially quantified variables.

16. ctr_see_also$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂}$ is a list of constraints that are related in some way to the constraint. Each element of the list is a fact of the form $\mathrm{𝚕𝚒𝚗𝚔}(\mathrm{𝚃𝚈𝙿𝙴}\_\mathrm{𝙾𝙵}\_\mathrm{𝙻𝙸𝙽𝙺},\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃},\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶},\mathrm{𝚂𝚈𝙼𝙱𝙾𝙻𝚂})$, where:

      • $\mathrm{𝚃𝚈𝙿𝙴}\_\mathrm{𝙾𝙵}\_\mathrm{𝙻𝙸𝙽𝙺}$ is a semantic link that explains why we refer to $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$. Semantic links were described in Section 2.6 on page 2.6.

      • $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}$ is the name of the constraint that is linked to $\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴}$.

      • $\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶}$ is a string providing contextual explanation.

      • $\mathrm{𝚂𝚈𝙼𝙱𝙾𝙻𝚂}$ is a list of symbols (e.g., keywords, constraint names, mathematical expressions) that are inserted in $\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶}$.

17. ctr_key_words$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙺𝙴𝚈𝚆𝙾𝚁𝙳𝚂})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙺𝙴𝚈𝚆𝙾𝚁𝙳𝚂}$ is a list of keywords associated with the constraint. Keywords may be linked to the meaning of the constraint, to a typical pattern where the constraint can be applied or to a specific problem where the constraint is useful. All keywords used in the catalogue are listed in alphabetic order in Section 3.7 on page 3.7. Each keyword has an entry explaining its meaning and providing the list of global constraints using that keyword.

18. ctr_eval$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙴𝚅𝙰𝙻𝚄𝙰𝚃𝙾𝚁𝚂})$

    • For many of the constraints of the catalogue one or several evaluators are provided. Each evaluator is explicitly described in $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙴𝚅𝙰𝙻𝚄𝙰𝚃𝙾𝚁𝚂}$ by an element of the form $\mathrm{𝚖𝚎𝚝𝚑𝚘𝚍}(\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎}\_\mathrm{𝚗𝚊𝚖𝚎})$, where $\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎}\_\mathrm{𝚗𝚊𝚖𝚎}$ is the name of the Prolog predicate to call in order to evaluate the constraint,Note that this predicate name should be different from existing SICStus built-ins, and $\mathrm{𝚖𝚎𝚝𝚑𝚘𝚍}$ can be one of the following keywords:

      • $\mathrm{𝚋𝚞𝚒𝚕𝚝𝚒𝚗}$ when the corresponding evaluator uses a SICStus built-in. This is for instance the case for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint.

      • $\mathrm{𝚛𝚎𝚏𝚘𝚛𝚖𝚞𝚕𝚊𝚝𝚒𝚘𝚗}$ when the corresponding evaluator reformulates the constraints in terms of a conjunction of constraints of the catalogue and/or in term of a conjunction of reified constraints. This is for instance the case for the $\mathrm{𝚝𝚛𝚎𝚎}$ constraint.

      • $\mathrm{𝚊𝚞𝚝𝚘𝚖𝚊𝚝𝚘𝚗}$ when the corresponding evaluator is based on an automaton that describes the set of solutions accepted by the constraint. The evaluator corresponds to the Prolog code that creates the signature constraints as well as the automata (usually one) associated with the constraint. A fact of the form automaton/9 lists the states and the transitions of the automata used for describing the set of solutions accepted by the constraint. It follows the description provided in Section 2.4.2 on page 2.4.2. The $\mathrm{𝚙𝚊𝚝𝚝𝚎𝚛𝚗}$ constraint is an example of constraint for which an automaton is provided.

      • $\mathrm{𝚕𝚘𝚐𝚒𝚌}$ when the corresponding evaluator is based on a first order logic formula that describes the meaning of the constraint. This is for instance the case for the $\mathrm{𝚖𝚎𝚎𝚝}\_\mathrm{𝚜𝚋𝚘𝚡𝚎𝚜}$ constraint.

      • $\mathrm{𝚌𝚑𝚎𝚌𝚔𝚎𝚛}$ when the corresponding evaluator only accepts ground instances of the constraint. This is for instance the case for the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint.

19. ctr_sol$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝚂𝙸𝚉𝙴},\mathrm{𝙼𝙸𝙽𝚅𝙰𝙻},\mathrm{𝙼𝙰𝚇𝚅𝙰𝙻},\mathrm{𝙽𝚂𝙾𝙻},\mathrm{𝙰𝚁𝙶}\_\mathrm{𝙽𝚂𝙾𝙻})$

    • $\mathrm{𝚂𝙸𝚉𝙴}$ is the number of variables of the collection of variables.

    • $\mathrm{𝙼𝙸𝙽𝚅𝙰𝙻}$ is the smallest value of the variables of the sequence of variables.

    • $\mathrm{𝙼𝙰𝚇𝚅𝙰𝙻}$ is the largest value of the variables of the sequence of variables.

    • $\mathrm{𝙽𝚂𝙾𝙻}$ is the total number of solutions of the constraint, assuming a collection with $\mathrm{𝚂𝙸𝚉𝙴}$ items and all variables within interval $[\mathrm{𝙼𝙸𝙽𝚅𝙰𝙻},\mathrm{𝙼𝙰𝚇𝚅𝙰𝙻}]$.

    • $\mathrm{𝙰𝚁𝙶}\_\mathrm{𝙽𝚂𝙾𝙻}$ is a list, which for each value that can be assigned to an argument of the constraint, gives the corresponding number of solutions assuming we have a collection with $\mathrm{𝚂𝙸𝚉𝙴}$ items, and that all variables of the collection are assigned a value in interval $[\mathrm{𝙼𝙸𝙽𝚅𝙰𝙻},\mathrm{𝙼𝙰𝚇𝚅𝙰𝙻}]$.

20. ctr_logic$(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}\_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙵𝙸𝚁𝚂𝚃}\_\mathrm{𝙾𝚁𝙳𝙴𝚁}\_\mathrm{𝙻𝙾𝙶𝙸𝙲}\_\mathrm{𝙵𝙾𝚁𝙼𝚄𝙻𝙰𝙴})$

    • $\mathrm{𝙻𝙸𝚂𝚃}\_\mathrm{𝙾𝙵}\_\mathrm{𝙵𝙸𝚁𝚂𝚃}\_\mathrm{𝙾𝚁𝙳𝙴𝚁}\_\mathrm{𝙻𝙾𝙶𝙸𝙲}\_\mathrm{𝙵𝙾𝚁𝙼𝚄𝙻𝙰𝙴}$ is a list of first order logical formulae that describe the meaning of the constraint [CarlssonBeldiceanuMartin08].