### 4.4.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_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]])).

ctr_see_also(minimum,

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

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

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]),

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).

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 15 items:

• Items 1, 2, 3, 4, 12 and 13 provide general information about a global constraint,

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

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

• Item 11 provides a ground instance which holds.

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

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

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

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

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

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

• $\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$\left(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝚄𝚂𝚄𝙰𝙻}_\mathrm{𝙽𝙰𝙼𝙴}\right)$

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

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

• $\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.1.1 and 2.1.2 on page 2.1.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 of 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$\left(\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃}_\mathrm{𝙽𝙰𝙼𝙴},\mathrm{𝙻𝙸𝚂𝚃}_\mathrm{𝙾𝙵}_\mathrm{𝙰𝚁𝙶𝚄𝙼𝙴𝙽𝚃𝚂}_\mathrm{𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂}\right)$

• $\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.1.1 and 2.1.2 on page 2.1.1.

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

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

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

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

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

• $\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.2.2.1 on page 2.2.2.1.

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

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

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

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

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

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

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

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

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

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

• $\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{𝚕𝚒𝚗𝚔}\left(\mathrm{𝚃𝚈𝙿𝙴}_\mathrm{𝙾𝙵}_\mathrm{𝙻𝙸𝙽𝙺},\mathrm{𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃},\mathrm{𝚂𝚃𝚁𝙸𝙽𝙶},\mathrm{𝚂𝚈𝙼𝙱𝙾𝙻𝚂}\right)$, where:

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

• $\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{𝚂𝚃𝚁𝙸𝙽𝙶}$.

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

• $\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.

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

• 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{𝚖𝚎𝚝𝚑𝚘𝚍}\left(\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎}_\mathrm{𝚗𝚊𝚖𝚎}\right)$, 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:

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

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