5.334. temporal_path

DESCRIPTIONLINKSGRAPH
Origin

ILOG

Constraint

πšπšŽπš–πš™πš˜πš›πšŠπš•_πš™πšŠπšπš‘(π™½π™Ώπ™°πšƒπ™·,π™½π™Ύπ™³π™΄πš‚)

Arguments
π™½π™Ώπ™°πšƒπ™·πšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›,πšœπšπšŠπš›πš-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Restrictions
π™½π™Ώπ™°πšƒπ™·β‰₯1
π™½π™Ώπ™°πšƒπ™·β‰€|π™½π™Ύπ™³π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌,πšœπšπšŠπš›πš,πšŽπš—πš])
|π™½π™Ύπ™³π™΄πš‚|>0
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
π™½π™Ύπ™³π™΄πš‚.πšœπšπšŠπš›πšβ‰€π™½π™Ύπ™³π™΄πš‚.πšŽπš—πš
Purpose

Let G be the digraph described by the π™½π™Ύπ™³π™΄πš‚ collection. Partition G 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
2,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-2πšœπšπšŠπš›πš-0πšŽπš—πš-1,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-6πšœπšπšŠπš›πš-3πšŽπš—πš-5,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-4πšœπšπšŠπš›πš-0πšŽπš—πš-3,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-5πšœπšπšŠπš›πš-4πšŽπš—πš-6,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-7πšœπšπšŠπš›πš-7πšŽπš—πš-8,πš’πš—πšπšŽπš‘-6𝚜𝚞𝚌𝚌-6πšœπšπšŠπš›πš-7πšŽπš—πš-9,πš’πš—πšπšŽπš‘-7𝚜𝚞𝚌𝚌-7πšœπšπšŠπš›πš-9πšŽπš—πš-10

The πšπšŽπš–πš™πš˜πš›πšŠπš•_πš™πšŠπšπš‘ constraint holds since:

  • The items of the π™½π™Ύπ™³π™΄πš‚ collection represent the two (π™½π™Ώπ™°πšƒπ™·=2) paths 1β†’2β†’6 and 3β†’4β†’5β†’7.

  • As illustrated by FigureΒ 5.334.1, all precedences between adjacent vertices of a same path hold: each item i (1≀i≀7) of the π™½π™Ύπ™³π™΄πš‚ collection is represented by a rectangle starting and ending at instants π™½π™Ύπ™³π™΄πš‚[i].πšœπšπšŠπš›πš and π™½π™Ύπ™³π™΄πš‚[i].πšŽπš—πš; the number within each rectangle designates the index of the corresponding item within the π™½π™Ύπ™³π™΄πš‚ collection.

Figure 5.334.1. The two paths of the Example slot represented as two sequences of rectangles
ctrs/temporal_path1
Symmetries
  • Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

  • One and the same constant can be added to the πšœπšπšŠπš›πš and πšŽπš—πš attributes of all items of π™½π™Ύπ™³π™΄πš‚.

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 i-th (1≀i≀|π™½π™Ύπ™³π™΄πš‚|) item of the π™½π™Ύπ™³π™΄πš‚ collection, we create a variable π‘†π‘‘π‘Žπ‘Ÿπ‘‘ 𝑠𝑒𝑐𝑐 𝑖 and an πšŽπš•πšŽπš–πšŽπš—πš(π™½π™Ύπ™³π™΄πš‚[i].𝚜𝚞𝚌𝚌,〈T i,1 ,T i,2 ,...,T i,π™½π™Ύπ™³π™΄πš‚ βŒͺ,π‘†π‘‘π‘Žπ‘Ÿπ‘‘ 𝑠𝑒𝑐𝑐 𝑖 ) constraint, where T i,j =π™½π™Ύπ™³π™΄πš‚[i].πšœπšπšŠπš›πš if iβ‰ j and T i,i =π™½π™Ύπ™³π™΄πš‚[i].πšŽπš—πš otherwise.

  • Finaly to the i-th (1≀i≀|π™½π™Ύπ™³π™΄πš‚|) item of the π™½π™Ύπ™³π™΄πš‚ collection, we also create an inequality constraint π™½π™Ύπ™³π™΄πš‚[i].πšŽπš—πšβ‰€π‘†π‘‘π‘Žπ‘Ÿπ‘‘ 𝑠𝑒𝑐𝑐 𝑖 . Note that, since T i,i was initialised to π™½π™Ύπ™³π™΄πš‚[i].πšŽπš—πš, the inequality π™½π™Ύπ™³π™΄πš‚[i].πšŽπš—πšβ‰€T i,j holds when i=j.

With respect to the Example slot we get the following conjunction of constraints:

Β Β Β πš™πšŠπšπš‘(2,βŒ©πš’πš—πšπšŽπš‘-1 𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-2 𝚜𝚞𝚌𝚌-6,πš’πš—πšπšŽπš‘-3 𝚜𝚞𝚌𝚌-4,

Β Β Β Β Β Β Β Β Β Β Β Β πš’πš—πšπšŽπš‘-4 𝚜𝚞𝚌𝚌-5,πš’πš—πšπšŽπš‘-5 𝚜𝚞𝚌𝚌-7,πš’πš—πšπšŽπš‘-6 𝚜𝚞𝚌𝚌-6,

Β Β Β Β Β Β Β Β Β Β Β Β πš’πš—πšπšŽπš‘-7 𝚜𝚞𝚌𝚌-7βŒͺ),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(2,〈1,3,0,4,7,7,9βŒͺ,3),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(6,〈1,5,0,4,7,7,9βŒͺ,7),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(4,〈1,5,3,4,7,7,9βŒͺ,4),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(5,〈1,5,3,6,7,7,9βŒͺ,7),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(7,〈1,5,3,6,8,7,9βŒͺ,9),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(6,〈1,5,3,6,8,9,9βŒͺ,9),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(7,〈1,5,3,6,8,9,10βŒͺ,10),

Β Β Β 1≀3, 5≀7, 3≀4, 6≀7, 8≀9, 9≀9, 10≀10.

See also

common keyword: πš™πšŠπšπš‘_πšπš›πš˜πš–_𝚝𝚘 (path).

specialisation: πš™πšŠπšπš‘Β (time dimension removed).

Keywords

combinatorial object: path.

constraint type: graph constraint, graph partitioning constraint.

final graph structure: connected component.

modelling: sequence dependent set-up.

modelling exercises: sequence dependent set-up.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

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

Arc arity
Arc constraint(s)
β€’ πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
β€’ πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘βˆ¨πš—πš˜πšπšŽπšœ1.πšŽπš—πšβ‰€πš—πš˜πšπšŽπšœ2.πšœπšπšŠπš›πš
β€’ πš—πš˜πšπšŽπšœ1.πšœπšπšŠπš›πšβ‰€πš—πš˜πšπšŽπšœ1.πšŽπš—πš
β€’ πš—πš˜πšπšŽπšœ2.πšœπšπšŠπš›πšβ‰€πš—πš˜πšπšŽπšœ2.πšŽπš—πš
Graph property(ies)
β€’ πŒπ€π—_πˆπƒ=1
β€’ 𝐍𝐂𝐂=π™½π™Ώπ™°πšƒπ™·
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚|

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 πŒπ€π—_πˆπƒ=1 enforces that each vertex has only one single predecessor (except the last vertex of a path that also has itself as a predecessor),

  • 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.334.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.334.2. Initial and final graph of the πšπšŽπš–πš™πš˜πš›πšŠπš•_πš™πšŠπšπš‘ constraint
ctrs/temporal_pathActrs/temporal_pathB
(a) (b)
Signature

Since we use the graph property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚| together with the restriction |π™½π™Ύπ™³π™΄πš‚|>0 the final graph is not empty. Therefore the smallest possible value of πŒπ€π—_πˆπƒ is equal to 1. So we can rewrite πŒπ€π—_πˆπƒ=1 to πŒπ€π—_πˆπƒβ‰€1 and simplify πŒπ€π—_πˆπƒ Β― Μ² to πŒπ€π—_πˆπƒ Μ².

Since the maximum number of vertices of the final graph is equal to |π™½π™Ύπ™³π™΄πš‚| we can rewrite the graph property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚| to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯|π™½π™Ύπ™³π™΄πš‚| and simplify 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β― Μ² to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―.