CHARME [OplobeduMarcovitchTourbier89]

$\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$

$\mathrm{𝚌𝚘𝚞𝚗𝚝}$, $\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚎}$, $\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚒𝚘𝚗}$, $\mathrm{𝚐𝚌𝚌}$, $\mathrm{𝚌𝚊𝚛𝚍}\_\mathrm{𝚟𝚊𝚛}\_\mathrm{𝚐𝚌𝚌}$, $\mathrm{𝚎𝚐𝚌𝚌}$, $\mathrm{𝚎𝚡𝚝𝚎𝚗𝚍𝚎𝚍}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$.

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint holds since values 3, 5 and 6 respectively occur 2, 0 and 1 times within the collection $\langle 3,3,8,6\rangle$ and since no constraint was specified for value 8.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be replaced by any other value that also does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$.

• All occurrences of two distinct values in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be swapped; all occurrences of a value in $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ or $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be renamed to any unused value.

We show how to use the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint in order to model the magic series problem [VanHentenryck89] with one single $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint. A non-empty finite series $S=(s_0,s_1,...,s_n)$ is magic if and only if there are $s_i$ occurrences of $i$ in $S$ for each integer $i$ ranging from 0 to $n$. This leads to the following model:

This is a generalised form of the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint: in the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint [Regin96], one specifies for each value its minimum and maximum number of occurrences (i.e., see $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$). Here we give for each value $v$ a domain variable that indicates how many time value $v$ is effectively used. By setting the minimum and maximum values of this variable to the appropriate constants we can express the same thing as in the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint. However, as shown in the magic series problem, we can also use this variable in other constraints. By reduction from 3-SAT, Claude -Guy Quimper shows in [Quimper03] that it is NP -hard to achieve arc-consistency for the count variables.

A last difference with the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint comes from the fact that there is no constraint on the values that are not explicitly mentioned in the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection. In the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ these values could not be assigned to the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. However allowing values that are not mentioned in $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ to be assigned to variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can potentially avoid mentioning a huge number of unconstrained values in the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection, and as a side effect, prevent eventuallyOf course one could also, while generating a flow model, detect all unconstrained values in order to generate one single vertex in the flow model for the set of unconstrained values. generating a dense graph (i.e., see DFS-bottleneck) for the corresponding underlying flow model).

Within [BourdaisGalinierPesant03] the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint is called $\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚒𝚘𝚗}$. Within [ReginGomes04] the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint is called $\mathrm{𝚌𝚊𝚛𝚍}\_\mathrm{𝚟𝚊𝚛}\_\mathrm{𝚐𝚌𝚌}$. Within [BessiereHebrardHnichWalsh04a] the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint is called $\mathrm{𝚎𝚐𝚌𝚌}$ or $\mathrm{𝚛𝚐𝚌𝚌}$. This later case corresponds to the fact that some variables are duplicated within the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint can be seen as a system (i.e., a conjunction) of $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraints.

When all count variables (i.e., the variables $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ with $i\in [1,|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left|\right]$) do not occur in any other constraints of the problem, it may be operationally more efficient to replace the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint by a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint where each count variable $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ is replaced by the corresponding interval $[\underline{\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}},\overline{\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}}]$. This stands for two reasons:

• First, by using a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint rather than a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint, we avoid the filtering algorithm related to the count variables.

• Second, unlike the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint where we need to fix all its variables to get entailment, the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ constraint can be entailed before all its variables get fixed. As a result, this potentially avoid unnecessary calls to its filtering algorithm.

An implicit necessary condition inferred by double counting with the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint is depicted by the following expression:

Within  [Pitrat08] the previous condition where terms involving identical variables are grouped together (i.e., rule 5 of MALICE [Pitrat01]) is mentioned as a crucial deduction rule for the autoref problem.

W.-J. van Hoeve et al. present two soft versions of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint in [HoevePesantRousseau04].

A flow algorithm that handles the original $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint is described in [Regin96]. The two approaches that were used to design bound-consistency algorithms for $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ were generalised for the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint. The algorithm in [QuimperBeekOrtizGolynskiSadjad03] identifies Hall intervals and the one in [KatrielThiel03] exploits convexity to achieve a fast implementation of the flow -based arc-consistency algorithm. The later algorithm can also compute bound-consistency for the count variables [KatrielThielConstraints05], [Katriel05]. An improved algorithm for achieving arc-consistency is described in [QuimperLopezOrtizBeekGolynski04].

globalCardinality in Choco, count in Gecode, gcc in JaCoP, global_cardinality in SICStus.

common keyword: $\mathrm{𝚌𝚘𝚞𝚗𝚝}$, $\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$, $\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ (value constraint,counting constraint), $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ (counting constraint),

$\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ (assignment,counting constraint).

cost variant: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ ($\mathrm{𝚌𝚘𝚜𝚝}$ associated with each $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$,$\mathrm{𝚟𝚊𝚕𝚞𝚎}$ pair).

implied by: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ (forget about cost), $\mathrm{𝚜𝚊𝚖𝚎}\_\mathrm{𝚊𝚗𝚍}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (conjoin $\mathrm{𝚜𝚊𝚖𝚎}$ and $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$).

part of system of constraints: $\mathrm{𝚊𝚖𝚘𝚗𝚐}$.

related: $\mathrm{𝚛𝚘𝚘𝚝𝚜}$, $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}\_\mathrm{𝚌𝚊𝚛𝚍}\_\mathrm{𝚜𝚔𝚒𝚙}\mathtt{0}$ (counting constraint of a set of values on maximal sequences).

shift of concept: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚗𝚘}\_\mathrm{𝚕𝚘𝚘𝚙}$ (assignment of a $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ to its position is ignored), $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (restrictions are done on nested sets of values, all starting from first value), $\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$, $\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚐𝚌𝚌}$.

soft variant: $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (a $\mathrm{𝚜𝚎𝚝}$ $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ defines the set of variables that are actually considered).

specialisation: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (each value should occur at most once), $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}$, $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}$ (individual $\mathrm{𝚌𝚘𝚞𝚗𝚝}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ for each value replaced by single $\mathrm{𝚌𝚘𝚞𝚗𝚝}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$), $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ (individual $\mathrm{𝚌𝚘𝚞𝚗𝚝}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ for each value replaced by single $\mathrm{𝚌𝚘𝚞𝚗𝚝}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ and $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$), $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚕𝚘𝚠}\_\mathrm{𝚞𝚙}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚏𝚒𝚡𝚎𝚍}$ $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$).

system of constraints: $\mathrm{𝚌𝚘𝚕𝚘𝚛𝚎𝚍}\_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$ (one $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint for each $\mathrm{𝚛𝚘𝚠}$ and each $\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}$ of a $\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$ of $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$).

uses in its reformulation: $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}$, $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$.

application area: assignment.

characteristic of a constraint: core, automaton, automaton with array of counters.

complexity: 3-SAT.

constraint type: value constraint, counting constraint, system of constraints.

filtering: Hall interval, bound-consistency, flow, duplicated variables, DFS-bottleneck.

modelling exercises: magic series.

puzzles: magic series, autoref.

For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$:

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Since we want to express one unary constraint for each value we use the “For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$” iterator. Part (A) of Figure 5.138.1 shows the initial graphs associated with each value 3, 5 and 6 of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection of the Example slot. Part (B) of Figure 5.138.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection (since value 5 is not assigned to any variable of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection the final graph associated with value 5 is empty). Since we use the $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ graph property, the vertices of the final graphs are stressed in bold.

Figure 5.138.1. Initial and final graph of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint

(a)	(b)

Figure 5.138.2 depicts the automaton associated with the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint. To each item of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${𝚂}_i$ that is equal to 0. To each item of the collection $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ corresponds a signature variable ${𝚂}_{i+\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|}$ that is equal to 1.

Figure 5.138.2. Automaton of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint