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,

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

and consists of the following Prolog facts, where 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙳𝙰𝚃𝙴𝚂_𝙾𝙵_𝙼𝙾𝙳𝙸𝙵𝙸𝙲𝙰𝚃𝙸𝙾𝙽𝚂 )

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

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

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

  3. ctr_usual_name( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝚄𝚂𝚄𝙰𝙻_𝙽𝙰𝙼𝙴 )

    • When, for some reason, the constraint name used in the catalogue does not correspond to the usual name of the constraint, 𝚄𝚂𝚄𝙰𝙻_𝙽𝙰𝙼𝙴 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 𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑 and the 𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚌𝚒𝚛𝚌𝚞𝚒𝚝 constraints which are both usually called 𝚜𝚝𝚛𝚎𝚝𝚌𝚑.

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

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

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚃𝚈𝙿𝙴𝚂_𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂 is a list of elements of the form 𝚗𝚊𝚖𝚎-𝚝𝚢𝚙𝚎, where 𝚗𝚊𝚖𝚎 is the name of a new type and 𝚝𝚢𝚙𝚎 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 𝚍𝚒𝚏𝚏𝚗 constraint where the unique argument 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 is a collection of 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴; 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 refers to a new type declared in 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚃𝚈𝙿𝙴𝚂_𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂.

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

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙰𝚁𝙶𝚄𝙼𝙴𝙽𝚃𝚂_𝙳𝙴𝙲𝙻𝙰𝚁𝙰𝚃𝙸𝙾𝙽𝚂 is a list of elements of the form 𝚊𝚛𝚐-𝚝𝚢𝚙𝚎, where 𝚊𝚛𝚐 is the name of an argument of the constraint and 𝚝𝚢𝚙𝚎 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂 )

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚁𝙴𝚂𝚃𝚁𝙸𝙲𝚃𝙸𝙾𝙽𝚂 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙴𝚂 )

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙴𝚂 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙳𝙴𝚁𝙸𝚅𝙴𝙳_𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂 )

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙳𝙴𝚁𝙸𝚅𝙴𝙳_𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙰𝚁𝙲_𝙸𝙽𝙿𝚄𝚃, 𝙰𝚁𝙲_𝙰𝚁𝙸𝚃𝚈,

                 𝙰𝚁𝙲_𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙾𝚁𝚂, 𝙰𝚁𝙲_𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂, 𝙶𝚁𝙰𝙿𝙷_𝙿𝚁𝙾𝙿𝙴𝚁𝚃𝙸𝙴𝚂 )

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙰𝚁𝙲_𝙸𝙽𝙿𝚄𝚃 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.

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

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

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

    • 𝙶𝚁𝙰𝙿𝙷_𝙿𝚁𝙾𝙿𝙴𝚁𝚃𝙸𝙴𝚂 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙴𝚇𝙰𝙼𝙿𝙻𝙴𝚂 )

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

  12. ctr_see_also( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃𝚂 )

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

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

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

      • 𝚂𝚃𝚁𝙸𝙽𝙶 is a string providing contextual explanation.

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

  13. ctr_key_words( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙺𝙴𝚈𝚆𝙾𝚁𝙳𝚂 )

    • 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙺𝙴𝚈𝚆𝙾𝚁𝙳𝚂 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( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙴𝚅𝙰𝙻𝚄𝙰𝚃𝙾𝚁𝚂 )

    • For many of the constraints of the catalogue one or several evaluators are provided. Each evaluator is explicitly described in 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙴𝚅𝙰𝙻𝚄𝙰𝚃𝙾𝚁𝚂 by an element of the form 𝚖𝚎𝚝𝚑𝚘𝚍(𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎_𝚗𝚊𝚖𝚎), where 𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎_𝚗𝚊𝚖𝚎 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 𝚖𝚎𝚝𝚑𝚘𝚍 can be one of the following keywords:

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

      • 𝚛𝚎𝚏𝚘𝚛𝚖𝚞𝚕𝚊𝚝𝚒𝚘𝚗 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 of the 𝚝𝚛𝚎𝚎 constraint.

      • 𝚊𝚞𝚝𝚘𝚖𝚊𝚝𝚘𝚗 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.3.2 on page 2.3.2. The 𝚙𝚊𝚝𝚝𝚎𝚛𝚗 constraint is an example of constraint for which an automaton is provided.

      • 𝚕𝚘𝚐𝚒𝚌 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 of the 𝚖𝚎𝚎𝚝_𝚜𝚋𝚘𝚡𝚎𝚜 constraint.

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

  15. ctr_logic( 𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃_𝙽𝙰𝙼𝙴, 𝙻𝙸𝚂𝚃_𝙾𝙵_𝙵𝙸𝚁𝚂𝚃_𝙾𝚁𝙳𝙴𝚁_𝙻𝙾𝙶𝙸𝙲_𝙵𝙾𝚁𝙼𝚄𝙻𝙰𝙴 )

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