5.400. temporal_path
| DESCRIPTION | LINKS | GRAPH |
- Origin
ILOG
- Constraint
- Arguments
- Restrictions
- Purpose
Let be the digraph described by the collection. Partition with a set of disjoint paths such that each vertex of the graph belongs to a single path. In addition, for all pairs of consecutive vertices of a path we have a precedence constraint that enforces the end associated with the first vertex to be less than or equal to the start related to the second vertex.
- Example
-
The constraint holds since:
The items of the collection represent the two () paths and .
As illustrated by FigureΒ 5.400.1, all precedences between adjacent vertices of a same path hold: each item () of the collection is represented by a rectangle starting and ending at instants and ; the number within each rectangle designates the index of the corresponding item within the collection.
Figure 5.400.1. The two paths of the Example slot represented as two sequences of tasks
- Typical
- Symmetries
Items of are permutable.
One and the same constant can be added to the and attributes of all items of .
- Arg. properties
Functional dependency: determined by .
- Remark
This constraint is related to the constraint of Ilog Solver. It can also be directly expressed with the Β [BeldiceanuContejean94] constraint of CHIP by using the diff nodes and the origin parameters. A generic model based on linear programming that handles paths, trees and cycles is presented in [LabbeLaporteRodriguezMartin98].
- Reformulation
The constraint can be expressed in term of a conjunction of one constraint, constraints, and inequalities constraints:
We pass to the constraint the number of path variable as well as the items of the collection form which we remove the and attributes.
To the -th item of the collection, we create a variable and an constraint, where if and otherwise.
Finaly to the -th item of the collection, we also create an inequality constraint . Note that, since was initialised to , the inequality holds when .
With respect to the Example slot we get the following conjunction of constraints:
Β Β Β Β Β Β Β Β Β Β Β Β
Β Β Β Β Β Β Β Β Β Β Β Β ,
Β Β Β , , , , , , .
- See also
common keyword: Β (path).
implies (items to collection): .
specialisation: Β (time dimension removed).
- Keywords
-
constraint type: graph constraint, graph partitioning constraint.
final graph structure: connected component.
modelling: sequence dependent set-up, functional dependency.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph model
The arc constraint is a conjunction of four conditions that respectively correspond to:
A constraint that links the successor variable of a first vertex to the index attribute of a second vertex,
A precedence constraint that applies on one vertex and its distinct successor,
One precedence constraint between the start and the end of the vertex that corresponds to the departure of an arc,
One precedence constraint between the start and the end of the vertex that corresponds to the arrival of an arc.
We use the following three graph properties in order to enforce the partitioning of the graph in distinct paths:
The first property enforces that each vertex has no more than one predecessor ( does not consider loops),
The second property ensures that we have the required number of paths,
The third property enforces that, for each vertex, the start is not located after the end.
PartsΒ (A) andΒ (B) of FigureΒ 5.400.2 respectively show the initial and final graph associated with the Example slot. Since we use the , the and the graph properties we display the following information on the final graph:
We show with a double circle a vertex that has the maximum number of predecessors.
We show the two connected components corresponding to the two paths.
We put in bold the vertices.
Figure 5.400.2. Initial and final graph of the constraint
(a) (b)