[HebrardMarxSullivanRazgon09]

$\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$

Within the collection $\langle 5,1,5,5\rangle$, 3 is the number of occurrences of the most assigned value. Consequently, the $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ constraint holds since the argument $𝙽=1$ is greater than or equal to the total number of variables 4 minus 3.

• $𝙽$ can be increased.

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

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

Let $m$ denote the total number of potential values that can be assigned to the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. In [HebrardMarxSullivanRazgon09], E. Hebrard et al. provides an $O\left(m\right)$ filtering algorithm achieving arc-consistency on the $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ constraint. The same paper also provides an algorithm with a lower complexity for achieving range consistency. Both algorithms are based on the following ideas:

• In a first phase, they both compute an envelope of the union $𝒟$ of the domains of the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection, i.e., an array $A$ that indicates for each potential value $v$ of $𝒟$, the maximum number of variables that could possibly be assigned value $v$. Let $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}$ denote the maximum value over the entries of array $A$, and let ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}$ denote the set of values which all occur in $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}$ variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. The quantity $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}$ is a lower bound of $𝙽$.

• In a second phase, depending on the relative ordering between $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}$ and the minimum value of $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-𝙽$, i.e., $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$, we have the three following cases:

  1. When $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}<\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$, the constraint $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ simply fails since not enough variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection can be assigned the same value.

  2. When $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}=\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$, the constraint $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ can be satisfied. In this context, a value $v$ can be removed from the domain of a variable $V$ of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection if and only if:

     1. value $v$ does not belong to ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}$,

     2. the domain of variable $V$ contains all values of ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}$.

     On the one hand, the first condition can be understand as the fact that value $v$ is not a value that allows to have at least $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$ variables assigned the same value. On the other hand, the second condition can be interpreted as the fact that variable $V$ is absolutely required in order to have at least $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$ variables assigned the same value.

  3. When $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}>\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}$, the constraint $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ can be satisfied, but no value can be pruned.

Note that, in the context of range consistency, the first phase of the filtering algorithm can be interpreted as a sweep algorithm were:

• On the one hand, the sweep status corresponds to the maximum number of occurrence of variables that can be assigned a given value.

• On the other hand, the event point series correspond to the minimum values of the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection as well as to the maximum values ($+1$) of the same variables.

Figure 5.301.1. Illustration of the two phases filtering algorithm

Figure 5.301.1 illustrates the previous filtering algorithm on an example where $𝙽$ is equal to 1, and where we have four variables $V_1$, $V_2$, $V_3$ and $V_4$ respectively taking their values within intervals $[1,3]$, $[3,7]$, $[0,8]$ and $[5,6]$ (see Part (A) of Figure 5.301.1, where the values of each variable are assigned a same colour that we retrieve in the other parts of Figure 5.301.1).

Part (B) of Figure 5.301.1 illustrates the first phase of the filtering algorithm, namely the computation of the envelope of the domains of variables $V_1$, $V_2$, $V_3$ and $V_4$. The start events $s_1$, $s_2$, $s_3$, $s_4$ (i.e., the events respectively associated with the minimum value of variables $V_1$, $V_2$, $V_3$, $V_4$) where the envelope is increased by 1 are represented by the character $\uparrow$. Similarly, the end events (i.e., the events $e_1$, $e_2$, $e_3$, $e_4$ respectively associated with the maximum value ($+1$) of $V_1$, $V_2$, $V_3$, $V_4$ are represented by the character $\downarrow$). Since the highest peak of the envelope is equal to 3 we have that $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}$ is equal to 3. The values that allow to reach this highest peak are equal to ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}=\{3,5,6\}$ (i.e., shown in red in Part (B) of Figure 5.301.1).

Finally, Part (C) of Figure 5.301.1 illustrates the second phase of the filtering algorithm. Since $\mathrm{𝑚𝑎𝑥}\_\mathrm{𝑜𝑐𝑐}=3$ is equal to $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|-\overline{𝙽}=4-1$ we remove from the variables whose domains contain ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}=\{3,5,6\}$ (i.e., variables $V_2$ and $V_3$) all values not in ${𝒱}_{\mathrm{𝑚𝑎𝑥}}\_\mathrm{𝑜𝑐𝑐}=\{3,5,6\}$ (i.e., values 4, 7 for variable $V_2$ and values 0, 1, 2, 4, 7, 8 for variable $V_3$).

common keyword: $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚊𝚡}\_\mathrm{𝚟𝚊𝚛}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚌𝚝𝚛}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚌𝚝𝚛}$, $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}\_\mathrm{𝚟𝚊𝚛}$ (soft constraint).

hard version: $\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}$.

related: $\mathrm{𝚊𝚝𝚖𝚘𝚜𝚝}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

constraint type: soft constraint, value constraint, relaxation, variable-based violation measure.

filtering: arc-consistency, sweep.

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

We generate an initial graph with binary equalities constraints between each vertex and its successors. The graph property states that $𝙽$ is greater than or equal to the difference between the total number of vertices of the initial graph and the number of vertices of the largest strongly connected component of the final graph.

Parts (A) and (B) of Figure 5.301.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐌𝐀𝐗}\_\mathrm{𝐍𝐒𝐂𝐂}$ graph property we show one of the largest strongly connected component of the final graph.

Figure 5.301.2. Initial and final graph of the $\mathrm{𝚜𝚘𝚏𝚝}\_\mathrm{𝚊𝚕𝚕}\_\mathrm{𝚎𝚚𝚞𝚊𝚕}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚟𝚊𝚛}$ constraint

(a)	(b)