## 5.46. balance_modulo

Origin
Constraint

$\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}\left(\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด},\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐},\mathrm{๐ผ}\right)$

Arguments
 $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}$ $\mathrm{๐๐๐๐}$ $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$ $\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐}-\mathrm{๐๐๐๐}\right)$ $\mathrm{๐ผ}$ $\mathrm{๐๐๐}$
Restrictions
 $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}โฅ0$ $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}โค\mathrm{๐๐๐ก}\left(0,|\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}|-2\right)$ $\mathrm{๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐},\mathrm{๐๐๐}\right)$ $\mathrm{๐ผ}>0$
Purpose

Consider the largest set ${\mathrm{๐ฎ}}_{1}$ (respectively the smallest set ${\mathrm{๐ฎ}}_{2}$) of variables of the collection $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$ that have the same remainder when divided by $\mathrm{๐ผ}$. $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}$ is equal to the difference between the cardinality of ${\mathrm{๐ฎ}}_{2}$ and the cardinality of ${\mathrm{๐ฎ}}_{1}$.

Example
$\left(2,โฉ6,1,7,1,5โช,3\right)$

In this example values 6, 1, 7, 1, 5 are respectively associated with the equivalence classes $6\mathrm{mod}3=0$, $1\mathrm{mod}3=1$, $7\mathrm{mod}3=1$, $1\mathrm{mod}3=1$, $5\mathrm{mod}3=2$. Therefore the equivalence classes 0, 1 and 2 are respectively used 1, 3 and 1 times. The $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}$ constraint holds since its first argument $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}$ is assigned to the difference between the maximum and minimum number of the previous occurrences (i.e.,ย $3-1$).

Typical
 $|\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}|>2$ $\mathrm{๐ผ}>1$ $\mathrm{๐ผ}<$$\mathrm{๐๐๐ก๐๐๐}$$\left(\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}.\mathrm{๐๐๐}\right)$
Symmetries
• Items of $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$ are permutable.

• An occurrence of a value $u$ of $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}.\mathrm{๐๐๐}$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $\mathrm{๐ผ}$.

Arg. properties

Functional dependency: $\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}$ determined by $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$ and $\mathrm{๐ผ}$.

Usage

An application of the $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}$ constraint is to enforce a balanced assignment of values, no matter how many distinct equivalence classes will be used. In this case one will push down the maximum value of the first argument of the $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}$ constraint.

specialisation: $\mathrm{๐๐๐๐๐๐๐}$ย ($\mathrm{๐๐๐๐๐๐๐๐}\mathrm{mod}\mathrm{๐๐๐๐๐๐๐๐}$ replaced by $\mathrm{๐๐๐๐๐๐๐๐}$).

Keywords
Arc input(s)

$\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$

Arc generator
$\mathrm{๐ถ๐ฟ๐ผ๐๐๐ธ}$$โฆ\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐๐๐๐}\mathtt{1},\mathrm{๐๐๐๐๐๐๐๐๐}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{๐๐๐๐๐๐๐๐๐}\mathtt{1}.\mathrm{๐๐๐}\mathrm{mod}\mathrm{๐ผ}=\mathrm{๐๐๐๐๐๐๐๐๐}\mathtt{2}.\mathrm{๐๐๐}\mathrm{mod}\mathrm{๐ผ}$
Graph property(ies)
$\mathrm{๐๐๐๐๐}_\mathrm{๐๐๐๐}$$=\mathrm{๐ฑ๐ฐ๐ป๐ฐ๐ฝ๐ฒ๐ด}$

Graph class
$\mathrm{๐ด๐๐๐ธ๐ ๐ฐ๐ป๐ด๐ฝ๐ฒ๐ด}$

Graph model

The graph property $\mathrm{๐๐๐๐๐}_\mathrm{๐๐๐๐}$ constraints the difference between the sizes of the largest and smallest strongly connected components.

Partsย (A) andย (B) of Figureย 5.46.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{๐๐๐๐๐}_\mathrm{๐๐๐๐}$ graph property, we show the largest and smallest strongly connected components of the final graph.

Automaton

Figureย 5.46.2 depicts the automaton associated with the $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}$ constraint. To each item of the collection $\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}$ corresponds a signature variable ${S}_{i}$ that is equal to 1.