## 5.19. among_low_up

Origin
Constraint

Arguments
 $\mathrm{\pi »\pi Ύ\pi }$ $\mathrm{\pi \pi \pi }$ $\mathrm{\pi \pi Ώ}$ $\mathrm{\pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi »\pi Ύ\pi }\beta ₯0$ $\mathrm{\pi »\pi Ύ\pi }\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi \pi Ώ}\beta ₯0$ $\mathrm{\pi \pi Ώ}\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi \pi Ώ}\beta ₯\mathrm{\pi »\pi Ύ\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

Between $\mathrm{\pi »\pi Ύ\pi }$ and $\mathrm{\pi \pi Ώ}$ variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection are assigned a value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection.

Example
$\left(\begin{array}{c}1,2,β©9,2,4,5βͺ,\hfill \\ β©0,2,4,6,8βͺ\hfill \end{array}\right)$

The constraint holds since between 1 and 2 values (i.e.,Β in fact 2 values) of the collection of values $\beta ©9,2,4,5\beta ͺ$ belong to the set of values $\left\{0,2,4,6,8\right\}$.

Typical
 $\mathrm{\pi »\pi Ύ\pi }<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi \pi Ώ}>0$ $\mathrm{\pi »\pi Ύ\pi }<\mathrm{\pi \pi Ώ}$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|>1$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• Items of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ are permutable.

• $\mathrm{\pi »\pi Ύ\pi }$ can be decreased to any value $\beta ₯0$.

• $\mathrm{\pi \pi Ώ}$ can be increased to any value $\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$.

• An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that belongs to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$ (resp. does not belong to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$) can be replaced by any other value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$ (resp. not in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$).

Algorithm

The constraint is entailed if and only if the following two conditions hold:

1. The number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection assigned a value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection is greater than or equal to $\mathrm{\pi »\pi Ύ\pi }$.

2. The number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection that can potentially be assigned a value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection is less than or equal to $\mathrm{\pi \pi Ώ}$.

Used in

generalisation: $\mathrm{\pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }\mathtt{0}$Β (full sequence replaced by maximal sequences of non -zeros).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$

Arc generator
$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi }\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }$
Graph property(ies)
 $\beta ’$$\mathrm{\pi \pi \pi \pi }$$\beta ₯\mathrm{\pi »\pi Ύ\pi }$ $\beta ’$$\mathrm{\pi \pi \pi \pi }$$\beta €\mathrm{\pi \pi Ώ}$

Graph class
 $\beta ’$$\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ $\beta ’$$\mathrm{\pi ±\pi Έ\pi Ώ\pi °\pi \pi \pi Έ\pi \pi ΄}$ $\beta ’$$\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$

Graph model

Each arc constraint of the final graph corresponds to the fact that a variable is assigned to a value that belong to the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection. The two graph properties restrict the total number of arcs to the interval $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$.

PartsΒ (A) andΒ (B) of FigureΒ 5.19.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ graph property, the arcs of the final graph are stressed in bold.

Automaton

FigureΒ 5.19.2 depicts the automaton associated with the constraint. To each variable ${\mathrm{\pi  \pi °\pi }}_{i}$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a 0-1 signature variable ${\mathrm{\pi }}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$ and ${\mathrm{\pi }}_{i}$: ${\mathrm{\pi  \pi °\pi }}_{i}\beta \mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\beta {\mathrm{\pi }}_{i}$. The automaton counts the number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection that take their value in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ and finally checks that this number is within the interval $\left[\mathrm{\pi »\pi Ύ\pi },\mathrm{\pi \pi Ώ}\right]$.