5.92. cycle_resource

DESCRIPTIONLINKSGRAPH
Origin

CHIP

Constraint

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

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

Consider a digraph G defined as follows:

  • To each item of the πšπ™΄πš‚π™Ύπš„πšπ™²π™΄ and πšƒπ™°πš‚π™Ί collections corresponds one vertex of G. A vertex that was generated from an item of the πšπ™΄πš‚π™Ύπš„πšπ™²π™΄ (respectively πšƒπ™°πš‚π™Ί) collection is called a resource vertex (respectively task vertex).

  • There is an arc from a resource vertex r to a task vertex t if tβˆˆπšπ™΄πš‚π™Ύπš„πšπ™²π™΄[r].πšπš’πš›πšœπš_πšπšŠπšœπš”.

  • There is an arc from a task vertex t to a resource vertex r if rβˆˆπšƒπ™°πš‚π™Ί[t].πš—πšŽπš‘πš_πšπšŠπšœπš”.

  • There is an arc from a task vertex t 1 to a task vertex t 2 if t 2 βˆˆπšƒπ™°πš‚π™Ί[t 1 ].πš—πšŽπš‘πš_πšπšŠπšœπš”.

  • There is no arc between two resource vertices.

Enforce to cover G in such a way that each vertex belongs to one single circuit. Each circuit is made up from one single resource vertex and zero, one or more task vertices. For each resource-vertex a domain variable indicates how many task-vertices belong to the corresponding circuit. For each task a domain variable provides the identifier of the resource that can effectively handle that task.

Example
πš’πš-1πšπš’πš›πšœπš_πšπšŠπšœπš”-5πš—πš‹_πšπšŠπšœπš”-3,πš’πš-2πšπš’πš›πšœπš_πšπšŠπšœπš”-2πš—πš‹_πšπšŠπšœπš”-0,πš’πš-3πšπš’πš›πšœπš_πšπšŠπšœπš”-8πš—πš‹_πšπšŠπšœπš”-2,πš’πš-4πš—πšŽπš‘πš_πšπšŠπšœπš”-7πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-5πš—πšŽπš‘πš_πšπšŠπšœπš”-4πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-6πš—πšŽπš‘πš_πšπšŠπšœπš”-3πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-3,πš’πš-7πš—πšŽπš‘πš_πšπšŠπšœπš”-1πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-1,πš’πš-8πš—πšŽπš‘πš_πšπšŠπšœπš”-6πš›πšŽπšœπš˜πšžπš›πšŒπšŽ-3

The πšŒπš’πšŒπš•πšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ constraint holds since the graph corresponding to the vertices described by its arguments consists of the following 3 disjoint circuits:

  • The first circuit involves the resource vertex 1 as well as the task vertices 5, 4 and 7.

  • The second circuit is limited to the resource vertex 2.

  • Finally the third circuit is made up from the remaining vertices, namely the resource vertex 3 and the task vertices 8 and 6.

Typical
|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|>1
|πšƒπ™°πš‚π™Ί|>1
|πšƒπ™°πš‚π™Ί|>|πšπ™΄πš‚π™Ύπš„πšπ™²π™΄|
Symmetries
  • Items of πšπ™΄πš‚π™Ύπš„πšπ™²π™΄ are permutable.

  • Items of πšƒπ™°πš‚π™Ί are permutable.

  • All occurrences of two distinct values in πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš or πšƒπ™°πš‚π™Ί.πš›πšŽπšœπš˜πšžπš›πšŒπšŽ can be swapped.

Usage

This constraint is useful for some vehicles routing problem where the number of locations to visit depends of the vehicle type that is effectively used. The resource attribute allows expressing various constraints such as:

  • The compatibility or incompatibility between tasks and vehicles,

  • The fact that certain tasks should be performed by the same vehicle,

  • The preassignment of certain tasks to a given vehicle.

Remark

This constraint could be expressed with the πšŒπš’πšŒπš•πšŽ constraint of CHIP by using the following optional parameters:

See also

common keyword: πšŒπš’πšŒπš•πšŽΒ (graph partitioning constraint).

Keywords

characteristic of a constraint: derived collection.

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

final graph structure: connected component, strongly connected component.

Derived Collection
πšŒπš˜πš•πšπ™΄πš‚π™Ύπš„πšπ™²π™΄_πšƒπ™°πš‚π™Ί-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›,πš—πšŠπš–πšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–πš’πš—πšπšŽπš‘-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš,𝚜𝚞𝚌𝚌-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πšπš’πš›πšœπš_πšπšŠπšœπš”,πš—πšŠπš–πšŽ-πšπ™΄πš‚π™Ύπš„πšπ™²π™΄.πš’πš,πš’πšπšŽπš–πš’πš—πšπšŽπš‘-πšƒπ™°πš‚π™Ί.πš’πš,𝚜𝚞𝚌𝚌-πšƒπ™°πš‚π™Ί.πš—πšŽπš‘πš_πšπšŠπšœπš”,πš—πšŠπš–πšŽ-πšƒπ™°πš‚π™Ί.πš›πšŽπšœπš˜πšžπš›πšŒπšŽ
Arc input(s)

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

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

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

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

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

The graph model of the πšŒπš’πšŒπš•πšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ constraint illustrates the following points:

  • How to differentiate the constraint on the length of a circuit according to a resource that is assigned to a circuit? This is achieved by introducing a collection of resources and by asking a different graph property for each item of that collection.

  • How to introduce the concept of name that corresponds to the resource that handles a given task? This is done by adding to the arc constraint associated with the πšŒπš’πšŒπš•πšŽ constraint the condition that the name variables of two consecutive vertices should be equal.

PartΒ (A) of FigureΒ 5.92.1 shows the initial graphs (of the second graph constraint) associated with resources 1, 2 and 3 of the Example slot. PartΒ (B) of FigureΒ 5.92.1 shows the corresponding final graphs (of the second graph constraint) 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 circuit of respectively 3, 0 and 2 task -vertices.

Figure 5.92.1. Initial and final graph of the πšŒπš’πšŒπš•πšŽ_πš›πšŽπšœπš˜πšžπš›πšŒπšŽ constraint
ctrs/cycle_resourceActrs/cycle_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 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―.