4.1. Differences from the 2000 report

This section summarises the main differences with the SICS report [Beldiceanu00] as well as of the corresponding article [BeldiceanuR00]. The main differences are listed below:

• We have both simplified and extended the way to generate the vertices of the initial graph and we have introduced a new way of defining set of vertices. We have also removed the $\mathrm{𝖢𝖫𝖨𝖰𝖴𝖤}\left(\mathrm{𝖬𝖠𝖷}\right)$ set of vertices generator since it cannot in general be evaluated in polynomial time. Therefore, we have modified the description of the constraints $\mathrm{𝚊𝚜𝚜𝚒𝚐𝚗}\_\mathrm{𝚊𝚗𝚍}\_\mathrm{𝚌𝚘𝚞𝚗𝚝𝚜}$, $\mathrm{𝚊𝚜𝚜𝚒𝚐𝚗}\_\mathrm{𝚊𝚗𝚍}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}\_\mathrm{𝚊𝚗𝚍}\_\mathrm{𝚌𝚘𝚞𝚗𝚝}$, $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}\_\mathrm{𝚊𝚗𝚍}\_\mathrm{𝚜𝚞𝚖}$, $\mathrm{𝚋𝚒𝚗}\_\mathrm{𝚙𝚊𝚌𝚔𝚒𝚗𝚐}$, $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$,

  $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$, $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$, $\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}\_\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜}$,

  $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}\_\mathrm{𝚝𝚠𝚘}\_𝚍$, which all used this feature.

• We have introduced the new arc generators $\mathrm{𝑃𝐴𝑇𝐻}\_\mathit{1}$ and $\mathrm{𝑃𝐴𝑇𝐻}\_𝑁$, which allow for specifying an $n$-ary constraint for which $n$ is not fixed.

  The $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ and the

  $\mathrm{𝚜𝚒𝚣𝚎}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚜𝚎𝚚}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ are examples of global constraints that use these arc generators in order to generate a set of sliding

  $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints.

• In addition to traditional domain variables we have introduced float, set and multiset variables as well as several global constraints mentioning float and set variables (see for instance the $\mathrm{𝚌𝚑𝚘𝚚𝚞𝚎𝚝}$  [LeHuedeGrabischLabreucheSaveant06] and the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}\_\mathrm{𝚜𝚎𝚝𝚜}$ constraints). This decision was initially motivated by the fact that several constraint systems and articles mention global constraints dealing with these types of variables. Later on, we realised that set variables also greatly simplify the interface of existing global constraints. This was especially true for those global constraints that explicitly deal with a graph, like $\mathrm{𝚌𝚕𝚒𝚚𝚞𝚎}$ or $\mathrm{𝚌𝚞𝚝𝚜𝚎𝚝}$. In this context, using a set variable for catching the successors of a vertex is quite natural. This is especially true when a vertex of the final graph can have more than one successor since it allows for avoiding a lot of 0-1 variables.

• We have introduced the possibility of using more than one graph constraint for defining a given global constraint (see for instance the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ or the $\mathrm{𝚜𝚘𝚛𝚝}$ constraints). Therefore we have removed the notion of dual graph, which was initially introduced in the original report. In this context, we now use two graph constraints (see for instance $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}\_\mathrm{𝚌𝚘𝚗𝚝𝚒𝚗𝚞𝚒𝚝𝚢}$).

• On the one hand, we have introduced the following new graph parameters:

  • $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐃𝐑𝐆}$,

  • $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐎𝐃}$,

  • $\mathrm{𝐌𝐈𝐍}\_\mathrm{𝐃𝐑𝐆}$,

  • $\mathrm{𝐌𝐈𝐍}\_\mathrm{𝐈𝐃}$,

  • $\mathrm{𝐌𝐈𝐍}\_\mathrm{𝐎𝐃}$,

  • $\mathrm{𝐍𝐓𝐑𝐄𝐄}$,

  • $\mathrm{𝐏𝐀𝐓𝐇}\_\mathrm{𝐅𝐑𝐎𝐌}\_\mathrm{𝐓𝐎}$,

  • $\mathrm{𝐏𝐑𝐎𝐃}$,

  • $\mathrm{𝐑𝐀𝐍𝐆𝐄}$,

  • $\mathrm{𝐑𝐀𝐍𝐆𝐄}\_\mathrm{𝐃𝐑𝐆}$,

  • $\mathrm{𝐑𝐀𝐍𝐆𝐄}\_\mathrm{𝐍𝐂𝐂}$,

  • $\mathrm{𝐒𝐔𝐌}$,

  • $\mathrm{𝐒𝐔𝐌}\_\mathrm{𝐖𝐄𝐈𝐆𝐇𝐓}\_\mathrm{𝐀𝐑𝐂}$.

  On the other hand, we have removed the following graph parameters:

  • $\mathrm{𝐍𝐂𝐂}(\mathrm{𝙲𝙾𝙼𝙿},\mathrm{𝚟𝚊𝚕})$,

  • $\mathrm{𝐍𝐒𝐂𝐂}(\mathrm{𝙲𝙾𝙼𝙿},\mathrm{𝚟𝚊𝚕})$,

  • $\mathrm{𝐍𝐓𝐑𝐄𝐄}(\mathrm{𝙰𝚃𝚃𝚁},\mathrm{𝙲𝙾𝙼𝙿},\mathrm{𝚟𝚊𝚕})$,

  • $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}\_\mathrm{𝐄𝐐}\_\mathrm{𝐍𝐒𝐈𝐍𝐊}$,

  • $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}\_\mathrm{𝐆𝐑𝐄𝐀𝐓𝐄𝐑𝐄𝐐}\_\mathrm{𝐍𝐒𝐈𝐍𝐊}$.

  Finally, $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐈𝐍}\_\mathrm{𝐃𝐄𝐆𝐑𝐄𝐄}$ has been renamed $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐈𝐃}$.

• We have introduced an iterator over the items of a collection in order to specify in a generic way a set of similar elementary constraints or a set of similar graph properties. This was required for describing some global constraints such as $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$ or $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$. All these global constraints mention a condition involving some limit depending on the specific values that are actually used. For instance the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint forces each value $v$ to be respectively used at least ${\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}}_v$ and at most ${\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}}_v$ times. This iterator was also necessary in the context of graph covering constraints where one wants to cover a digraph with some patterns. Each pattern consists of one resource and several tasks. One can now attach specific constraints to the different resources. Both the $\mathrm{𝚌𝚢𝚌𝚕𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$ and the $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$ constraints illustrate this point.

• We have added some standard existing global constraints that were obviously missing from the previous report. This was for instance the case of the $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint.

• In order to make clear the notion of family of global constraints we have computed for each global constraint a signature, which summarises its structure. Each signature was inserted into the index so that one can retrieve all the global constraints sharing the same structure.

• We have generalised some existing global constraints. For instance the $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}\_\mathrm{𝚙𝚊𝚒𝚛}$ constraint extends the $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ constraint. Finally we have introduced some novel global constraints like $\mathrm{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\_\mathrm{𝚝𝚊𝚜𝚔𝚜}$ or $\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚐𝚌𝚌}$.

• We have defined the rules for specifying arc constraints.