18.104.22.168. 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 . 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 22.214.171.124 on page 126.96.36.199).
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.
generates all elementary pathsA path where all vertices are distinct is called an elementary path. of 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
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.
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 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 and a task is an overlapping constraint that holds if both, the duration of is strictly greater than zero, and if the origin of is overlapped by task .
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
Parts (A) and (B) of Figure 2.2.6 respectively show the initial and the final graph corresponding to the following instance:
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 , , , and . 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: