5.39. balance_partition

Origin
Constraint

$\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}\left(\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}\right)$

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

Consider the largest set ${𝒮}_{1}$ (respectively the smallest set ${𝒮}_{2}$) of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that take their value in the same partition of the collection $\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}.\mathrm{𝙱𝙰𝙻𝙰𝙽𝙲𝙴}$ is equal to the difference between the cardinality of ${𝒮}_{2}$ and the cardinality of ${𝒮}_{1}$.

Example
$\left(\begin{array}{c}1,〈6,2,6,4,4〉,\hfill \\ 〈\begin{array}{c}𝚙-〈1,3〉,\hfill \\ 𝚙-〈4〉,\hfill \\ 𝚙-〈2,6〉\hfill \end{array}〉\hfill \end{array}\right)$

In this example values $6,2,6,4,4$ are respectively associated with the partitions $𝚙-〈2,6〉$ and $𝚙-〈4〉$. Partitions $𝚙-〈4〉$ and $𝚙-〈2,6〉$ are respectively used 2 and 3 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-2$). Note that we do not consider those partitions that are not used at all.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}|$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Items of $\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}$ are permutable.

• Items of $\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}.𝚙$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be replaced by any other value that also belongs to the same partition of $\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}$.

Usage

An application of the $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$ is to enforce a balanced assignment of values, no matter how many distinct partitions 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{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}\in \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{𝚒𝚗}_\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$$\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛},\mathrm{𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽𝚂}\right)$
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.39.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.