Derived from $\mathrm{𝚝𝚛𝚎𝚎}$.

$\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}(\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂},𝚁,\mathrm{𝙽𝙾𝙳𝙴𝚂})$

The $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}$ constraint holds since the graph associated with the items of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection corresponds to two trees (i.e., $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}=2$): each tree respectively involves the vertices $\{1,2,3,5,6,8\}$ and $\{4,7\}$. Furthermore $𝚁=1$ is set to the difference between the longest path (for instance $2\to 5\to 1$) and the shortest path (for instance $4\to 7$) from a leaf to a root. Figure 5.404.1 provides the two trees associated with the example.

Figure 5.404.1. The two trees corresponding to the Example slot; each vertex contains the information $\mathrm{𝚒𝚗𝚍𝚎𝚡}|\mathrm{𝚜𝚞𝚌𝚌}$ where $\mathrm{𝚜𝚞𝚌𝚌}$ is the index of its father in the tree (by convention the father of the root is the root itself); the longest and shortest paths from a leaf to a root are respectively shown by thick orange and yellow line segments and have a length of 2 and 1; consequently the range is equal to 1.

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

• Functional dependency: $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ determined by $\mathrm{𝙽𝙾𝙳𝙴𝚂}$.

• Functional dependency: $𝚁$ determined by $\mathrm{𝙽𝙾𝙳𝙴𝚂}$.

By introducing a distance variable $D_i$, an occurrence variable $O_i$ and a leave variable $L_i$ $(1\le i\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}\left|\right)$ for each item $i$ of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection, where:

• $D_i$ represents the number of vertices from $i$ to the root of the corresponding tree,

• $O_i$ gives the number of occurrences of value $i$ within variables $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[1\right].\mathrm{𝚜𝚞𝚌𝚌},\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[2\right].\mathrm{𝚜𝚞𝚌𝚌},\cdots ,\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[n\right].\mathrm{𝚜𝚞𝚌𝚌}$,

• $L_i$ is set to 1 if item $i$ corresponds to a leave (i.e., $O_i>0$) and 0 otherwise,

the $\mathrm{𝚝𝚛𝚎𝚎}\_\mathrm{𝚛𝚊𝚗𝚐𝚎}$$(\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂},𝚁,\mathrm{𝙽𝙾𝙳𝙴𝚂})$ constraint can be expressed in term of a conjunction of one $\mathrm{𝚝𝚛𝚎𝚎}$ constraint, $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints, $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ linear constraints, one $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint, $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ reified constraints, one $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$, one $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ and one linear constraint, where:

• The $\mathrm{𝚝𝚛𝚎𝚎}$ constraint models the fact that we have a forest of $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ trees.

• Each $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint provides the link between the attribute $\mathrm{𝚜𝚞𝚌𝚌}$ of the $i$-th item and the distance variable $D_{\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}}$ associated with item $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}$.

• Each linear constraint associated with the $i$-th item states that the difference between the distance variable $D_i$ and the distance variable $D_{\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[i\right].\mathrm{𝚜𝚞𝚌𝚌}}$ is equal to 1.

• The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint provides the number of occurrences $O_i$ of value $i$ $(1\le i\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}\left|\right)$ within variables $\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[1\right].\mathrm{𝚜𝚞𝚌𝚌},\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[2\right].\mathrm{𝚜𝚞𝚌𝚌},\cdots ,\mathrm{𝙽𝙾𝙳𝙴𝚂}\left[\right|\mathrm{𝙽𝙾𝙳𝙴𝚂}\left|\right].\mathrm{𝚜𝚞𝚌𝚌}$. Note that, when $O_i$ is equal to 0, the corresponding $i$-th item is a leave of one of the $\mathrm{𝙽𝚃𝚁𝙴𝙴𝚂}$ trees.

• Each reified constraint of the form $L_i\iff O_i>0$ makes the link between the $i$-th occurrence variable $O_i$ and the $i$-th leave variable $L_i$.

• The $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint computes the minimum distance $\mathrm{𝙼𝙸𝙽}$ from the leaves to the corresponding roots. The leave variable $L_i$ is used in order to select only the distance variables corresponding to leaves.

• The $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ constraint computes the maximum distance $\mathrm{𝙼𝙰𝚇}$ from the vertices to the roots. Since the maximum is achieved by a leave we do not need to focus just on the leaves as it was the case for the minimum distance $\mathrm{𝙼𝙸𝙽}$.

• The linear constraint $\mathrm{𝙼𝙰𝚇}-\mathrm{𝙼𝙸𝙽}=𝚁$ links together argument $𝚁$ to the minimum and maximum distances.

With respect to the Example slot we get the following conjunction of constraints:

   $\mathrm{𝚝𝚛𝚎𝚎}$$(2,\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-1\mathrm{𝚜𝚞𝚌𝚌}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-2\mathrm{𝚜𝚞𝚌𝚌}-5,$

            $\mathrm{𝚒𝚗𝚍𝚎𝚡}-3\mathrm{𝚜𝚞𝚌𝚌}-5,\mathrm{𝚒𝚗𝚍𝚎𝚡}-4\mathrm{𝚜𝚞𝚌𝚌}-7,$

            $\mathrm{𝚒𝚗𝚍𝚎𝚡}-5\mathrm{𝚜𝚞𝚌𝚌}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-6\mathrm{𝚜𝚞𝚌𝚌}-1,$

            $\mathrm{𝚒𝚗𝚍𝚎𝚡}-7\mathrm{𝚜𝚞𝚌𝚌}-7,\mathrm{𝚒𝚗𝚍𝚎𝚡}-8\mathrm{𝚜𝚞𝚌𝚌}-5\rangle )$,

   $\mathrm{𝚍𝚘𝚖𝚊𝚒𝚗}$$(\langle D_1,D_2,D_3,D_4,D_5,D_6,D_7,D_8\rangle ,0,8)$,

   $D{S}_1\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 0,D_2,D_3,D_4,D_5,D_6,D_7,D_8\rangle ,D{S}_1)$,  $D_1-0=1$,

   $D{S}_2\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(5,\langle 1,0,D_3,D_4,D_5,D_6,D_7,D_8\rangle ,D{S}_2)$,  $D_2-D_5=1$,

   $D{S}_3\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(5,\langle 1,D_2,0,D_4,D_5,D_6,D_7,D_8\rangle ,D{S}_3)$,  $D_3-D_5=1$,

   $D{S}_4\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(7,\langle 1,D_2,D_3,0,D_5,D_6,D_7,D_8\rangle ,D{S}_4)$,  $D_4-D_7=1$,

   $D{S}_5\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 1,D_2,D_3,D_4,0,D_6,D_7,D_8\rangle ,D{S}_5)$,  $D_5-1=1$,

   $D{S}_6\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 1,3,3,D_4,2,0,D_7,D_8\rangle ,D{S}_6)$,  $D_6-1=1$,

   $D{S}_7\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(7,\langle 1,3,3,D_4,2,2,0,D_8\rangle ,D{S}_7)$,  $D_7-0=1$,

   $D{S}_8\in [0,8]$,  $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(5,\langle 1,3,3,2,2,2,1,0\rangle ,D{S}_8)$,  $D_8-2=1$,

   $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$(\langle 1,5,5,7,1,1,7,5\rangle ,\langle \mathrm{𝚟𝚊𝚕}-1\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-3,$

                                                  $\mathrm{𝚟𝚊𝚕}-2\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,$

                                                  $\mathrm{𝚟𝚊𝚕}-3\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,$

                                                  $\mathrm{𝚟𝚊𝚕}-4\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,$

                                                  $\mathrm{𝚟𝚊𝚕}-5\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-3,$

                                                  $\mathrm{𝚟𝚊𝚕}-6\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,$

                                                  $\mathrm{𝚟𝚊𝚕}-7\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-2,$

                                                  $\mathrm{𝚟𝚊𝚕}-8\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0\rangle )$,

   $1\iff 3>0,0\iff 0>0,0\iff 0>0,0\iff 0>0,$

   $1\iff 3>0,0\iff 0>0,1\iff 2>0,0\iff 0>0$,

   $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$$(\mathrm{𝙼𝙸𝙽},\langle \mathrm{𝚟𝚊𝚛}-3\mathrm{𝚋𝚘𝚘𝚕}-1,\mathrm{𝚟𝚊𝚛}-0\mathrm{𝚋𝚘𝚘𝚕}-0,$

                         $\mathrm{𝚟𝚊𝚛}-0\mathrm{𝚋𝚘𝚘𝚕}-0,\mathrm{𝚟𝚊𝚛}-0\mathrm{𝚋𝚘𝚘𝚕}-0,$

                         $\mathrm{𝚟𝚊𝚛}-3\mathrm{𝚋𝚘𝚘𝚕}-1,\mathrm{𝚟𝚊𝚛}-0\mathrm{𝚋𝚘𝚘𝚕}-0,$

                         $\mathrm{𝚟𝚊𝚛}-2\mathrm{𝚋𝚘𝚘𝚕}-1,\mathrm{𝚟𝚊𝚛}-0\mathrm{𝚋𝚘𝚘𝚕}-0\rangle )$,

   $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$$(\mathrm{𝙼𝙰𝚇},\langle 1,3,3,2,2,2,1,3\rangle )$,

   $\mathrm{𝙼𝙰𝚇}-\mathrm{𝙼𝙸𝙽}=𝚁=1$.

related: $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}$ (balanced tree versus balanced assignment).

root concept: $\mathrm{𝚝𝚛𝚎𝚎}$.

used in reformulation: $\mathrm{𝚍𝚘𝚖𝚊𝚒𝚗}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$, $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$, $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$, $\mathrm{𝚘𝚙𝚎𝚗}\_\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$, $\mathrm{𝚝𝚛𝚎𝚎}$.

constraint type: graph constraint, graph partitioning constraint.

final graph structure: connected component, tree.

modelling: balanced tree, functional dependency.