Global Constraint Catalog: Ctree

5.405. tree_resource

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚝𝚛𝚎𝚎$ .

Constraint

$𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 (𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴, 𝚃𝙰𝚂𝙺)$

Arguments

$𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍 - 𝚒𝚗𝚝, 𝚗𝚋_𝚝𝚊𝚜𝚔 - 𝚍𝚟𝚊𝚛)$
$𝚃𝙰𝚂𝙺$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍 - 𝚒𝚗𝚝, 𝚏𝚊𝚝𝚑𝚎𝚛 - 𝚍𝚟𝚊𝚛, 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 𝚍𝚟𝚊𝚛)$

Restrictions

| 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴, [𝚒𝚍, 𝚗𝚋_𝚝𝚊𝚜𝚔])

𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍 \geq 1

𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍 \leq | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴, 𝚒𝚍)

𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚗𝚋_𝚝𝚊𝚜𝚔 \geq 0

𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚗𝚋_𝚝𝚊𝚜𝚔 \leq | 𝚃𝙰𝚂𝙺 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝚂𝙺, [𝚒𝚍, 𝚏𝚊𝚝𝚑𝚎𝚛, 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎])

𝚃𝙰𝚂𝙺 . 𝚒𝚍 > | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 |

𝚃𝙰𝚂𝙺 . 𝚒𝚍 \leq | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚃𝙰𝚂𝙺, 𝚒𝚍)

𝚃𝙰𝚂𝙺 . 𝚏𝚊𝚝𝚑𝚎𝚛 \geq 1

𝚃𝙰𝚂𝙺 . 𝚏𝚊𝚝𝚑𝚎𝚛 \leq | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |

𝚃𝙰𝚂𝙺 . 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 \geq 1

𝚃𝙰𝚂𝙺 . 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 \leq | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 |

Purpose

Cover a digraph $G$ in such a way that each vertex belongs to one distinct tree. Each tree is made up from one resource vertex and several task vertices. The resource vertices correspond to the roots of the different trees. For each resource a domain variable $𝚗𝚋_𝚝𝚊𝚜𝚔$ indicates how many task-vertices belong to the corresponding tree. For each task a domain variable $𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ gives the identifier of the resource that can handle the task.

Example

(\begin{matrix} 〈\begin{matrix} 𝚒𝚍 - 1 & 𝚗𝚋_𝚝𝚊𝚜𝚔 - 4, \\ 𝚒𝚍 - 2 & 𝚗𝚋_𝚝𝚊𝚜𝚔 - 0, \\ 𝚒𝚍 - 3 & 𝚗𝚋_𝚝𝚊𝚜𝚔 - 1 \end{matrix}〉, \\ 〈\begin{matrix} 𝚒𝚍 - 4 & 𝚏𝚊𝚝𝚑𝚎𝚛 - 8 & 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 1, \\ 𝚒𝚍 - 5 & 𝚏𝚊𝚝𝚑𝚎𝚛 - 3 & 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 3, \\ 𝚒𝚍 - 6 & 𝚏𝚊𝚝𝚑𝚎𝚛 - 8 & 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 1, \\ 𝚒𝚍 - 7 & 𝚏𝚊𝚝𝚑𝚎𝚛 - 1 & 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 1, \\ 𝚒𝚍 - 8 & 𝚏𝚊𝚝𝚑𝚎𝚛 - 1 & 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 - 1 \end{matrix}〉 \end{matrix})

The $𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ constraint holds since the graph associated with the items of the $𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴$ and the $𝚃𝙰𝚂𝙺$ collections corresponds to 3 trees (i.e., $| 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | = 3$ ): each tree respectively involves the vertices ${1, 4, 6, 7, 8}$ , ${2}$ and ${3, 5}$ . They are depicted by Figure 5.405.1, where resource and task vertices are respectively coloured in blue and pink.

Figure 5.405.1. The three trees corresponding to the Example slot; each resource vertex (in blue) contains the information $𝚒𝚍 | 𝚗𝚋_𝚝𝚊𝚜𝚔$ where $𝚗𝚋_𝚝𝚊𝚜𝚔$ is the number of tasks in the tree, while each task vertex (in pink) contains the information $𝚒𝚍 | 𝚏𝚊𝚝𝚑𝚎𝚛 | 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ where $𝚏𝚊𝚝𝚑𝚎𝚛$ is the index of its father in the tree and $𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ is the index of the corresponding root task in the tree.

Typical

| 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | > 0

| 𝚃𝙰𝚂𝙺 | > | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 |

Symmetries

Items of $𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴$ are permutable.
Items of $𝚃𝙰𝚂𝙺$ are permutable.

Reformulation

The $𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ $(𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴, 𝚃𝙰𝚂𝙺)$ constraint can be expressed in term of a conjunction of one $𝚝𝚛𝚎𝚎$ constraint, $| 𝚃𝙰𝚂𝙺 |$ $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraints and one $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint:

The $𝚝𝚛𝚎𝚎$ constraint expresses the fact that we have a well formed tree.
The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint is used for expressing the link between the $𝚏𝚊𝚝𝚑𝚎𝚛$ attribute of an item of the $𝚃𝙰𝚂𝙺$ collection and its corresponding $𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ attribute.
The $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint is used to link the $𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ attribute of the items of the $𝚃𝙰𝚂𝙺$ collection with the $𝚗𝚋_𝚝𝚊𝚜𝚔$ attribute of the items of the $𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴$ collection.

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

$𝚝𝚛𝚎𝚎$ $(3, 〈 𝚒𝚗𝚍𝚎𝚡 - 1 𝚜𝚞𝚌𝚌 - 1,$

$𝚒𝚗𝚍𝚎𝚡 - 2 𝚜𝚞𝚌𝚌 - 2,$

$𝚒𝚗𝚍𝚎𝚡 - 3 𝚜𝚞𝚌𝚌 - 3,$

$𝚒𝚗𝚍𝚎𝚡 - 4 𝚜𝚞𝚌𝚌 - 8,$

$𝚒𝚗𝚍𝚎𝚡 - 5 𝚜𝚞𝚌𝚌 - 3,$

$𝚒𝚗𝚍𝚎𝚡 - 6 𝚜𝚞𝚌𝚌 - 8,$

$𝚒𝚗𝚍𝚎𝚡 - 7 𝚜𝚞𝚌𝚌 - 1,$

$𝚒𝚗𝚍𝚎𝚡 - 8 𝚜𝚞𝚌𝚌 - 1 〉)$ ,

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(8, 〈 1, 2, 3, 1, 3, 1, 1, 1 〉, 1)$ ,

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 1, 2, 3, 1, 3, 1, 1, 1 〉, 3)$ ,

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(8, 〈 1, 2, 3, 1, 3, 1, 1, 1 〉, 1)$ ,

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(1, 〈 1, 2, 3, 1, 3, 1, 1, 1 〉, 1)$ ,

$𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ $(〈 1, 3, 1, 1, 1 〉,$

$〈 𝚟𝚊𝚕 - 1 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 4,$

$𝚟𝚊𝚕 - 2 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 0,$

$𝚟𝚊𝚕 - 3 𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎 - 1 〉)$ .

See also

root concept: $𝚝𝚛𝚎𝚎$ .

used in reformulation: $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ , $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ , $𝚝𝚛𝚎𝚎$ .

Keywords

characteristic of a constraint: derived collection.

constraint type: graph constraint, resource constraint, graph partitioning constraint.

final graph structure: tree, connected component.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴_𝚃𝙰𝚂𝙺 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, \\ 𝚜𝚞𝚌𝚌 - 𝚍𝚟𝚊𝚛, \\ 𝚗𝚊𝚖𝚎 - 𝚍𝚟𝚊𝚛 \end{matrix}), \\ [\begin{matrix} 𝚒𝚝𝚎𝚖 (\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍, \\ 𝚜𝚞𝚌𝚌 - 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍, \\ 𝚗𝚊𝚖𝚎 - 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍 \end{matrix}), \\ 𝚒𝚝𝚎𝚖 (\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 𝚃𝙰𝚂𝙺 . 𝚒𝚍, \\ 𝚜𝚞𝚌𝚌 - 𝚃𝙰𝚂𝙺 . 𝚏𝚊𝚝𝚑𝚎𝚛, \\ 𝚗𝚊𝚖𝚎 - 𝚃𝙰𝚂𝙺 . 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 \end{matrix}) \end{matrix}] \end{matrix})

Arc input(s)

$𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴_𝚃𝙰𝚂𝙺$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1, 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2)

Arc arity

Arc constraint(s)

• 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1 . 𝚜𝚞𝚌𝚌 = 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2 . 𝚒𝚗𝚍𝚎𝚡

• 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1 . 𝚗𝚊𝚖𝚎 = 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2 . 𝚗𝚊𝚖𝚎

Graph property(ies)

•

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

\leq 1

•

𝐍𝐂𝐂

= | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 |

•

𝐍𝐕𝐄𝐑𝐓𝐄𝐗

= | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |

For all items of $𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴$ :

Arc input(s)

$𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴_𝚃𝙰𝚂𝙺$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1, 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2)

Arc arity

Arc constraint(s)

• 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1 . 𝚜𝚞𝚌𝚌 = 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2 . 𝚒𝚗𝚍𝚎𝚡

• 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1 . 𝚗𝚊𝚖𝚎 = 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 2 . 𝚗𝚊𝚖𝚎

• 𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎_𝚝𝚊𝚜𝚔 1 . 𝚗𝚊𝚖𝚎 = 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚒𝚍

Graph property(ies)

𝐍𝐕𝐄𝐑𝐓𝐄𝐗

= 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 . 𝚗𝚋_𝚝𝚊𝚜𝚔 + 1

Graph model

For the second graph constraint, part (A) of Figure 5.405.2 shows the initial graphs associated with resources 1, 2 and 3 of the Example slot. For the second graph constraint, part (B) of Figure 5.405.2 shows the corresponding final graphs associated with resources 1, 2 and 3. Since we use the $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ graph property, the vertices of the final graphs are stressed in bold. To each resource corresponds a tree of respectively 4, 0 and 1 task-vertices.

Figure 5.405.2. Initial and final graph of the $𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ constraint


(a)	(b)

Signature

Since the initial graph of the first graph constraint contains $| 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |$ vertices, the corresponding final graph cannot have more than $| 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |$ vertices. Therefore we can rewrite the graph property $𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |$ to $𝐍𝐕𝐄𝐑𝐓𝐄𝐗 \geq | 𝚁𝙴𝚂𝙾𝚄𝚁𝙲𝙴 | + | 𝚃𝙰𝚂𝙺 |$ and simplify $\underset{̲}{\bar{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}}$ to $\bar{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.405. tree_resource

Figure 5.405.2. Initial and final graph of the 𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎 constraint

Figure 5.405.2. Initial and final graph of the $𝚝𝚛𝚎𝚎_𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎$ constraint