2.2.3.2. Dynamic graph constraint

The purpose of a dynamic graph constraint is to enforce a condition on different subsets of variables, not known in advance. This situation occurs frequently in practice and is hard to express since one cannot use a classical constraint for which it is required to provide all variables right from the beginning. One good example of such global constraint is the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint where one wants to force the sum of some variables to be less than or equal to a given limit. In the context of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint, each set of variables is defined by the height of the different tasks that overlap a given instant i. Since the origins of the tasks are not initially fixed, we do not know in advance which task will overlap a given instant and so, we cannot state any sum constraint initially.

A dynamic graph constraint is defined in exactly the same way as a simple graph constraint, except that we may omit the Graph property(ies) slot, and that we have to provide the two following additional slots:

  • The Set slot denotes a generator of sets of vertices. Such a generator takes as argument a final graph and produces different sets of vertices. In order to have something tractable, we force the total number of generated sets to be polynomial in the number of vertices.

    In practice each set of vertices is represented by a collection of items. The type of this collection corresponds either to the type of the items associated with the vertices, or to the type of a new derived collection. This is achieved by providing an expression of the form πš—πšŠπš–πšŽ or πš—πšŠπš–πšŽ-πšπšŽπš›πš’πšŸπšŽπš_πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—, where πš—πšŠπš–πšŽ represents a formal parameter, and πšπšŽπš›πš’πšŸπšŽπš_πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš— a declaration of a new derived collection (as specified in SectionΒ 2.2.2.1 on page 2.2.2.1).

  • The Constraint(s) on sets slot provides a global constraint defined in the catalogue that has to hold for each set created by the previous generator.

We now describe the different generators of sets of vertices currently available:

  • 𝖠𝖫𝖫_𝖡𝖀𝖱𝖳𝖨𝖒𝖀𝖲 generates one single set containing all the vertices of the final graph. It is specified by a declaration of the form

    𝖠𝖫𝖫_𝖡𝖀𝖱𝖳𝖨𝖒𝖀𝖲>>[πšŸπšŽπš›πšπš’πšŒπšŽπšœ]

    where πšŸπšŽπš›πšπš’πšŒπšŽπšœ represents all the vertices of the final graph.

  • 𝖒𝖒 generates one set of vertices for each connected component of the final graph. These sets correspond to all the vertices of a given connected component. It is specified by a declaration of the form

    𝖒𝖒>>[πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš_πšŒπš˜πš–πš™πš˜πš—πšŽπš—πš]

    where πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš_πšŒπš˜πš–πš™πš˜πš—πšŽπš—πš represents the vertices of a connected component of the final graph.

  • 𝖯𝖠𝖳𝖧_𝖫𝖀𝖭𝖦𝖳𝖧(L) generates all elementary pathsA path where all vertices are distinct is called an elementary path. of L vertices of the final graph such that, discarding loops, all vertices of a path (except the last one) have no more than one successor in the final graph. It is specified by a declaration of the form

    𝖯𝖠𝖳𝖧_𝖫𝖀𝖭𝖦𝖳𝖧(L)>>[πš™πšŠπšπš‘]

    where πš™πšŠπšπš‘ represents the vertices of an elementary path, ordered according to their occurrence in the path.

  • 𝖯𝖱𝖀𝖣 generates the non -empty sets corresponding to the predecessors of each vertex of the final graph. It is specified by a declaration of the form

    𝖯𝖱𝖀𝖣>>[πš™πš›πšŽπšπšŽπšŒπšŽπšœπšœπš˜πš›,πšπšŽπšœπšπš’πš—πšŠπšπš’πš˜πš—]

    where πšπšŽπšœπšπš’πš—πšŠπšπš’πš˜πš— represents a vertex of the final graph and πš™πš›πšŽπšπšŽπšŒπšŽπšœπšœπš˜πš› its predecessors.

  • 𝖲𝖴𝖒𝖒 generates the non -empty sets corresponding to the successors of each vertex of the final graph. It is specified by a declaration of the form

    𝖲𝖴𝖒𝖒>>[πšœπš˜πšžπš›πšŒπšŽ,πšœπšžπšŒπšŒπšŽπšœπšœπš˜πš›]

    where πšœπš˜πšžπš›πšŒπšŽ represents a vertex of the final graph and πšœπšžπšŒπšŒπšŽπšœπšœπš˜πš› its successors.

As an illustrative example of dynamic graph constraint we now consider the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint.

EXAMPLE: The πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚,π™»π™Έπ™Όπ™Έπšƒ) constraint, where πšƒπ™°πš‚π™Ίπš‚ is a collection of the form πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’πšπš’πš—-πšπšŸπšŠπš›,πšπšžπš›πšŠπšπš’πš˜πš—-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›, πš‘πšŽπš’πšπš‘πš-πšπšŸπšŠπš›), and where π™»π™Έπ™Όπ™Έπšƒ is a non -negative integer, holds if, for any point the cumulated height of the set of tasks that overlap that point, does not exceed π™»π™Έπ™Όπ™Έπšƒ.

The first graph constraint of πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ enforces for each task of the πšƒπ™°πš‚π™Ίπš‚ collection the equality πš˜πš›πš’πšπš’πš—+πšπšžπš›πšŠπšπš’πš˜πš—=πšŽπš—πš. We focus on the second graph constraint, which uses a dynamic graph constraint described by the following items:

Arc input(s)Β Β Β Β Β Β Β :

πšƒπ™°πš‚π™Ίπš‚ πšƒπ™°πš‚π™Ίπš‚

Arc generatorΒ Β Β Β Β :

π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšŠπšœπš”πšœ1,πšπšŠπšœπš”πšœ2)

Arc arityΒ Β Β Β Β Β Β Β Β Β :

2

Arc constraint(s)Β Β Β :

πšπšŠπšœπš”πšœ1.πšπšžπš›πšŠπšπš’πš˜πš—>0

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β 

πšπšŠπšœπš”πšœ2.πš˜πš›πš’πšπš’πš—β‰€πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β 

πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—β‰€πšπšŠπšœπš”πšœ2.πšŽπš—πš

SetsΒ Β Β Β Β Β Β Β Β Β Β Β Β Β :

𝖲𝖴𝖒𝖒>>

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β [πšœπš˜πšžπš›πšŒπšŽ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β [πš’πšπšŽπš–(πšŸπšŠπš›-πšƒπ™°πš‚π™Ίπš‚.πš‘πšŽπš’πšπš‘πš)])]

Constraint(s) on sets:

πšœπšžπš–_πšŒπšπš›(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,≀,π™»π™Έπ™Όπ™Έπšƒ)

The second graph constraint is defined by:

  • To each item of the πšƒπ™°πš‚π™Ίπš‚ collection correspond two vertices of the initial graph.

  • The arity of the arc constraint is 2.

  • The arcs of the initial graph are constructed with the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator between the πšƒπ™°πš‚π™Ίπš‚ collection and the πšƒπ™°πš‚π™Ίπš‚ collection. Therefore, each vertex associated with a task is linked to all the vertices related to the different tasks.

  • The arc constraint that is associated with an arc between a task πšπšŠπšœπš”πšœ1 and a task πšπšŠπšœπš”πšœ2 is an overlapping constraint that holds if both, the duration of πšπšŠπšœπš”πšœ1 is strictly greater than zero, and if the origin of πšπšŠπšœπš”πšœ1 is overlapped by task πšπšŠπšœπš”πšœ2.

  • The set generator is 𝖲𝖴𝖒𝖒. The final graph will consist of those tasks for which the origin is covered by at least one task and of those corresponding tasks.

  • The dynamic constraint on a set forces the sum of the heights of the tasks that belong to a successor set to not exceed π™»π™Έπ™Όπ™Έπšƒ.

Figure 2.2.6. Initial and final graph of an instance of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint
ctrs/cumulative_graphs

Parts (A) and (B) of FigureΒ 2.2.6 respectively show the initial and the final graph corresponding to the following instance:

πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ(βŒ©πš˜πš›πš’πšπš’πš—-1 πšπšžπš›πšŠπšπš’πš˜πš—-3 πš‘πšŽπš’πšπš‘πš-1,

πš˜πš›πš’πšπš’πš—-2 πšπšžπš›πšŠπšπš’πš˜πš—-9 πš‘πšŽπš’πšπš‘πš-2,

πš˜πš›πš’πšπš’πš—-3 πšπšžπš›πšŠπšπš’πš˜πš—-10 πš‘πšŽπš’πšπš‘πš-1,

πš˜πš›πš’πšπš’πš—-6 πšπšžπš›πšŠπšπš’πš˜πš—-6 πš‘πšŽπš’πšπš‘πš-1,

πš˜πš›πš’πšπš’πš—-7 πšπšžπš›πšŠπšπš’πš˜πš—-2 πš‘πšŽπš’πšπš‘πš-3βŒͺ,8).

We label the vertices of the initial and final graph by giving the πš”πšŽπš’πš”πšŽπš’ is an implicit attribute corresponding to the position of an item within a collection that was introduced in SectionΒ 2.1.2 on page 2.1.2. of the corresponding task. On both graphs the edges are oriented from left to right. On the final graph we consider the sets that consist of the successors of the different vertices; those are the sets of tasks {1}, {1,2}, {1,2,3}, {2,3,4} and {2,3,4,5}. Since the 𝖲𝖴𝖒𝖒 set generator uses a derived collection that only considers the πš‘πšŽπš’πšπš‘πš attribute of a task, these sets respectively correspond to the following collection of items:

  • βŒ©πšŸπšŠπš›-1βŒͺ,

  • βŒ©πšŸπšŠπš›-1, πšŸπšŠπš›-2βŒͺ,

  • βŒ©πšŸπšŠπš›-1, πšŸπšŠπš›-2, πšŸπšŠπš›-1βŒͺ,

  • βŒ©πšŸπšŠπš›-2, πšŸπšŠπš›-1, πšŸπšŠπš›-1βŒͺ,

  • βŒ©πšŸπšŠπš›-2, πšŸπšŠπš›-1, πšŸπšŠπš›-1, πšŸπšŠπš›-3βŒͺ.

The πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint holds since, for each successors set, the corresponding constraint holds:

The πšœπšžπš–_πšŒπšπš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš,πš…π™°πš) constraint holds if the sum πš‚ of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection satisfies πš‚ π™²πšƒπš πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, where π™²πšƒπš is a comparison operator.