## 5.36. balance

 DESCRIPTION LINKS GRAPH AUTOMATON
Origin

N. Beldiceanu

Constraint

$\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}\left(\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}\ge 0$ $\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}\le \mathrm{𝚖𝚊𝚡}\left(0,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-2\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

$\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}$ is equal to the difference between the number of occurrence of the value that occurs the most and the value that occurs the least within the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Example
$\left(2,〈3,1,7,1,1〉\right)$

In this example, values $1,3$ and 7 are respectively used $3,1$ and 1 times. The $\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$). Figure 5.36.1 shows the solution associated with the example.

##### Figure 5.36.1. Illustration of the example: five variables respectively fixed to values 3, 1, 7, 1 and 1, and the corresponding value of $\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}=2$ Typical
$|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$
Symmetries
• 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.

Usage

An application of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint is to enforce a balanced assignment of values, no matter how many distinct values will be used. In this case one will push down the maximum value of the first argument of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint.

Remark

If we do not want to use an automaton with an array of counters a possible reformulation of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint can be achieved in the following way. We use a $\mathrm{𝚜𝚘𝚛𝚝}$ constraint in order to reorder the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ and compute the difference between the longest and the smallest sequences of consecutive values.

See also

generalisation: $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}/\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$), $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}_\mathrm{𝚖𝚘𝚍𝚞𝚕𝚘}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\mathrm{mod}\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$), $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$).

related: $\mathrm{𝚝𝚛𝚎𝚎}_\mathrm{𝚛𝚊𝚗𝚐𝚎}$ (balanced assignment versus balanced tree).

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{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\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.36.2 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.

##### Figure 5.36.2. Initial and final graph of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint  (a) (b)
Automaton

Figure 5.36.3 depicts the automaton associated with the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint. To each item of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${𝚂}_{i}$ that is equal to 1.

##### Figure 5.36.3. Automaton of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ constraint 