5.339. tree_resource

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšπš›πšŽπšŽ.

Constraint

πšπš›πšŽπšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ(πšπ™΄πš‚π™Ύπš„πšπ™²π™΄,πšƒπ™°πš‚π™Ί)

Arguments
πšπ™΄πš‚π™Ύπš„πšπ™²π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πš—πš‹_πšπšŠπšœπš”-πšπšŸπšŠπš›)
πšƒπ™°πš‚π™ΊπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πšπšŠπšπš‘πšŽπš›-πšπšŸπšŠπš›,πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-πšπšŸπšŠπš›)
Restrictions
|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πšπ™΄πš‚π™Ύπš„πšπ™²π™΄,[πš’πš,πš—πš‹_πšπšŠπšœπš”])
πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πšβ‰₯1
πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πšβ‰€|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|
πšπš’πšœπšπš’πš—πšŒπš(πšπ™΄πš‚π™Ύπš„πšπ™²π™΄,πš’πš)
πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš—πš‹_πšπšŠπšœπš”β‰₯0
πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš—πš‹_πšπšŠπšœπš”β‰€|πšƒπ™°πš‚π™Ί|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°πš‚π™Ί,[πš’πš,πšπšŠπšπš‘πšŽπš›,πš›πšŽπšœπš˜πšžπš›πšŒπšŽ])
πšƒπ™°πš‚π™Ί.πš’πš>|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|
πšƒπ™°πš‚π™Ί.πš’πšβ‰€|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|+|πšƒπ™°πš‚π™Ί|
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°πš‚π™Ί,πš’πš)
πšƒπ™°πš‚π™Ί.πšπšŠπšπš‘πšŽπš›β‰₯1
πšƒπ™°πš‚π™Ί.πšπšŠπšπš‘πšŽπš›β‰€|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|+|πšƒπ™°πš‚π™Ί|
πšƒπ™°πš‚π™Ί.πš›πšŽπšœπš˜πšžπš›πšŒπšŽβ‰₯1
πšƒπ™°πš‚π™Ί.πš›πšŽπšœπš˜πšžπš›πšŒπšŽβ‰€|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|
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
πš’πš-1 πš—πš‹_πšπšŠπšœπš”-4,πš’πš-2 πš—πš‹_πšπšŠπšœπš”-0,πš’πš-3 πš—πš‹_πšπšŠπšœπš”-1,πš’πš-4πšπšŠπšπš‘πšŽπš›-8πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-5πšπšŠπšπš‘πšŽπš›-3πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-3,πš’πš-6πšπšŠπšπš‘πšŽπš›-8πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-7πšπšŠπšπš‘πšŽπš›-1πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-8πšπšŠπšπš‘πšŽπš›-1πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1

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.339.1, where resource and task vertices are respectively coloured in blue and pink.

Figure 5.339.1. The three trees associated with the example
ctrs/tree_resource1
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:

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,〈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
πšŒπš˜πš•πšπ™΄πš‚π™Ύπš„πšπ™²π™΄_πšƒπ™°πš‚π™Ί-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›,πš—πšŠπš–πšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–πš’πš—πšπšŽπš‘-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš,𝚜𝚞𝚌𝚌-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš,πš—πšŠπš–πšŽ-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš,πš’πšπšŽπš–πš’πš—πšπšŽπš‘-πšƒπ™°πš‚π™Ί.πš’πš,𝚜𝚞𝚌𝚌-πšƒπ™°πš‚π™Ί.πšπšŠπšπš‘πšŽπš›,πš—πšŠπš–πšŽ-πšƒπ™°πš‚π™Ί.πš›πšŽπšœπš˜πšžπš›πšŒπšŽ
Arc input(s)

πšπ™΄πš‚π™Ύπš„πšπ™²π™΄_πšƒπ™°πš‚π™Ί

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”1,πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”2)

Arc arity
Arc constraint(s)
β€’ πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”1.𝚜𝚞𝚌𝚌=πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”2.πš’πš—πšπšŽπš‘
β€’ πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”1.πš—πšŠπš–πšŽ=πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”2.πš—πšŠπš–πšŽ
Graph property(ies)
β€’ πŒπ€π—_𝐍𝐒𝐂𝐂≀1
β€’ 𝐍𝐂𝐂=|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|+|πšƒπ™°πš‚π™Ί|

For all items of πšπ™΄πš‚π™Ύπš„πšπ™²π™΄:

Arc input(s)

πšπ™΄πš‚π™Ύπš„πšπ™²π™΄_πšƒπ™°πš‚π™Ί

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš›πšŽπšœπš˜πšžπš›πšŒπšŽ_πšπšŠπšœπš”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.339.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.339.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.339.2. Initial and final graph of the πšπš›πšŽπšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ constraint
ctrs/tree_resourceActrs/tree_resourceB
(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 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|+|πšƒπ™°πš‚π™Ί| and simplify 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β― Μ² to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―.