2.2.2.2. Elementary constraints attached to the arcs

This section describes the constraints that are associated with the arcs of the initial graph of a global constraint. These constraints are called arc constraints. To each arc one can associate one or several arc constraints. An arc will belong to the final graph if and only if all its arc constraints hold. An arc constraint from a vertex v 1 to a vertex v 2 mentions variables and/or values associated with v 1 and v 2 . Before defining an arc constraint, we first need to introduce simple arithmetic expressions as well as arithmetic expressions. Simple arithmetic expressions and arithmetic expressions are defined recursively.

Simple arithmetic expressions

A simple arithmetic expression is defined by one of the five following expressions.

  • I: I is an integer.

  • π™°πš›πš: π™°πš›πš is an argument of the global constraint of type πš’πš—πš or πšπšŸπšŠπš›.

  • π™°πš›πš: π™°πš›πš is a formal parameter provided by the arc generatorArc generators are described in SectionΒ 2.2.2.3 on page 2.2.2.3. of the graph -constraint.

  • π™²πš˜πš•.π™°πšπšπš›: π™²πš˜πš• is a formal parameter provided by the arc generator or the collection used in the π™΅πš˜πš› πšŠπš•πš• πš’πšπšŽπš–πšœ 𝚘𝚏 iterator.The π™΅πš˜πš› πšŠπš•πš• πš’πšπšŽπš–πšœ 𝚘𝚏 iterator is described in SectionΒ 2.2.3.1 on page 2.2.3.1. π™°πšπšπš› is an attribute of the collection referenced by π™²πš˜πš•.

    EXAMPLE: As an example consider the first graph -constraint associated with the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ) constraint and its arc constraint πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš› =πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•. Both, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš› as well as πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• are simple arithmetic expressions of the form π™²πš˜πš•.π™°πšπšπš›:

    • In πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ corresponds to the formal parameter provided by the arc generator π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ), while πšŸπšŠπš› is an attribute of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

    • In πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•, πš…π™°π™»πš„π™΄πš‚ corresponds to the collection denoted by the π™΅πš˜πš› πšŠπš•πš• πš’πšπšŽπš–πšœ 𝚘𝚏 iterator, while πšŸπšŠπš• is an attribute of the πš…π™°π™»πš„π™΄πš‚ collection.

  • π™²πš˜πš•[π™΄πš‘πš™πš›].π™°πšπšπš›: π™²πš˜πš• is an argument of type πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—, π™°πšπšπš› one attribute of π™²πš˜πš• and π™΄πš‘πš™πš› an arithmetic expression.

    π™²πš˜πš•[π™΄πš‘πš™πš›].π™°πšπšπš› denotes the value of attribute π™°πšπšπš› of the π™΄πš‘πš™πš› th item of the collection denoted by π™²πš˜πš•.

    EXAMPLE: As an example consider the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš πš’πšπš‘_𝚌𝚘𝚜𝚝𝚜( πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚,π™Όπ™°πšƒπšπ™Έπš‡,π™²π™Ύπš‚πšƒ) constraint and its second graph -constraint, which defines the π™²π™Ύπš‚πšƒ variable. The expression π™Όπ™°πšƒπšπ™Έπš‡[(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’-1)*|πš…π™°π™»πš„π™΄πš‚|+ πšŸπšŠπš•πšžπšŽπšœ.πš”πšŽπš’].𝚌 is a simple arithmetic expression of the form π™²πš˜πš•[π™΄πš‘πš™πš›].π™°πšπšπš›:

    • π™Όπ™°πšƒπšπ™Έπš‡ is a collection of items πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’-πš’πš—πš,πš“-πš’πš—πš,𝚌-πš’πš—πš) where all items are sorted in increasing order on attributes πš’,πš“ (because of the restriction πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(π™Όπ™°πšƒπšπ™Έπš‡,[πš’,πš“])).

    • π™Όπ™°πšƒπšπ™Έπš‡[(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’-1)*|πš…π™°π™»πš„π™΄πš‚|+πšŸπšŠπš•πšžπšŽπšœ.πš”πšŽπš’].𝚌 denotes the value of attribute 𝚌 of an item of the π™Όπ™°πšƒπšπ™Έπš‡ collection. The position of this item within the π™Όπ™°πšƒπšπ™Έπš‡ collection depends on the position of a variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collectionThis position is denoted by the expression πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’. As defined in SectionΒ 2.1.2 on page 2.1.2, πš”πšŽπš’ is an implicit attribute corresponding to the position of an item within a collection. as well as on the position of a value of the πš…π™°π™»πš„π™΄πš‚ collection.This position is denoted by the expression πšŸπšŠπš•πšžπšŽπšœ.πš”πšŽπš’.

Arithmetic expressions

An arithmetic expression is recursively defined by one of the following expressions:

  • A simple arithmetic expression.

  • π™΄πš‘πš™ 1 π™Ύπš™ π™΄πš‘πš™ 2
    • π™΄πš‘πš™ 1 is an arithmetic expression,

    • π™Ύπš™ is one of the following symbols +, -, *, // denotes an integer division, a division in which the fractional part is discarded.,

    • π™΄πš‘πš™ 2 is an arithmetic expression.

  • |π™²πš˜πš•πš•πšŽπšŒπšπš’πš˜πš—|
    • π™²πš˜πš•πš•πšŽπšŒπšπš’πš˜πš— is an argument of type πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš— and |π™²πš˜πš•πš•πšŽπšŒπšπš’πš˜πš—| denotes the number of items of that collection.

  • |π™΄πš‘πš™|
    • π™΄πš‘πš™ is an arithmetic expression, and |π™΄πš‘πš™| denotes the absolute value of this expression.

  • πšœπš’πšπš—(π™΄πš‘πš™)

    • π™΄πš‘πš™ is an arithmetic expression, and πšœπš’πšπš—(π™΄πš‘πš™) the sign of π™΄πš‘πš™ (-1 if π™΄πš‘πš™ is negative, 0 if π™΄πš‘πš™ is equal to 0, 1 if π™΄πš‘πš™ is positive).

    EXAMPLE: An example of use of πšœπš’πšπš— can be found in the last part of the arc constraint of the πšŒπš›πš˜πšœπšœπš’πš—πš constraint:

    πšœπš’πšπš—((𝚜2.𝚘𝚑-𝚜1.𝚎𝚑)*(𝚜1.𝚎𝚒-𝚜1.𝚘𝚒)-(𝚜1.𝚎𝚑-𝚜1.𝚘𝚑)*(𝚜2.𝚘𝚒-𝚜1.𝚎𝚒))β‰ 

    πšœπš’πšπš—((𝚜2.𝚎𝚑-𝚜1.𝚎𝚑)*(𝚜2.𝚘𝚒-𝚜1.𝚘𝚒)-(𝚜2.𝚘𝚑-𝚜1.𝚘𝚑)*(𝚜2.𝚎𝚒-𝚜1.𝚎𝚒))

  • πšŒπšŠπš›πš_𝚜𝚎𝚝(πš‚πšŽπš):

    • πš‚πšŽπš is a reference to a set of integers or to a set variable. πšŒπšŠπš›πš_𝚜𝚎𝚝(πš‚πšŽπš) denotes the number of elements of that set.

    EXAMPLE: An example of use of πšŒπšŠπš›πš_𝚜𝚎𝚝 can be found in the πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌 constraint: πšŸπšŠπš›πšœ.πš—πš˜πšŒπšŒ=πšŒπšŠπš›πš_𝚜𝚎𝚝(πšŸπšŠπš›πšœ.πšŸπšŠπš›).

  • πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 1 mod πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 2 ,

    min(πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 1 ,πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 2 ) or max(πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 1 ,πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 2 )

    • πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 1 is a simple arithmetic expression,

    • πš‚πš’πš–πš™πš•πšŽπ™΄πš‘πš™ 2 is a simple arithmetic expression.

Arc constraints

Now that we have introduced simple arithmetic expressions as well as arithmetic expressions we define an arc constraint. An arc constraint is recursively defined by one of the following expressions:

  • πšƒπšπš„π™΄

    This stands for an arc constraint that always holds. As a result, the corresponding arc always belongs to the final graph.

    EXAMPLE: An example of use of πšƒπšπš„π™΄ can be found in the πšœπšžπš–_πšŒπšπš›(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, π™²πšƒπš, πš…π™°πš) constraint, where it is used in order to enforce keeping all items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection in the final graph.

  • π™΄πš‘πš™ 1 π™²πš˜πš–πš™πšŠπš›πš’πšœπš˜πš— π™΄πš‘πš™ 2
    • π™΄πš‘πš™ 1 is an arithmetic expression,

    • π™²πš˜πš–πš™πšŠπš›πš’πšœπš˜πš— is one of the comparison operators ≀, β‰₯, <, >, =, β‰ ,

    • π™΄πš‘πš™ 2 is an arithmetic expression.

    EXAMPLE: As an example of such arc constraint, the second graph -constraint of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚,π™»π™Έπ™Όπ™Έπšƒ) constraint uses the following arc constraints:

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

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

    • πšπšŠπšœπš”πšœ1.πš˜πš›πš’πšπš’πš—<πšπšŠπšœπš”πšœ2.πšŽπš—πš.

    The conjunction of these three arc constraints can be interpreted in the following way: an arc from a task πšπšŠπšœπš”πšœ1 to a task πšπšŠπšœπš”πšœ2 will belong to the final graph if and only if πšπšŠπšœπš”πšœ2 overlaps the origin of πšπšŠπšœπš”πšœ1.

  • π™΄πš‘πš™ 1 πš‚πš’πš–πš™πš•πšŽπ™²πšπš› π™΄πš‘πš™ 2
    • π™΄πš‘πš™ 1 is an arithmetic expression,

    • πš‚πš’πš–πš™πš•πšŽπ™²πšπš› is an argument of type πšŠπšπš˜πš– that can only take one of the values ≀, β‰₯, <, >, =, β‰ ,

    • π™΄πš‘πš™ 2 is an arithmetic expression.

    EXAMPLE: An example of use of such an arc constraint can be found in the πšŒπš‘πšŠπš—πšπšŽ(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš) constraint: πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› π™²πšƒπš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›. Within this expression, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2 correspond to consecutive items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

  • π™΄πš‘πš™ 1 Β¬πš‚πš’πš–πš™πš•πšŽπ™²πšπš› π™΄πš‘πš™ 2
    • π™΄πš‘πš™ 1 is an arithmetic expression,

    • πš‚πš’πš–πš™πš•πšŽπ™²πšπš› is an argument of type πšŠπšπš˜πš– that can only take one of the values ≀, β‰₯, <, >, =, β‰ ,

    • π™΄πš‘πš™ 2 is an arithmetic expression.

    EXAMPLE: An example of use of such an arc constraint can be found in the πšŒπš‘πšŠπš—πšπšŽ_πšŒπš˜πš—πšπš’πš—πšžπš’πšπš’(𝙽𝙱_π™Ώπ™΄πšπ™Έπ™Ύπ™³_𝙲𝙷𝙰𝙽𝙢𝙴, 𝙽𝙱_π™Ώπ™΄πšπ™Έπ™Ύπ™³_π™²π™Ύπ™½πšƒπ™Έπ™½πš„π™Έπšƒπšˆ, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄_𝙲𝙷𝙰𝙽𝙢𝙴, π™Όπ™°πš‡_πš‚π™Έπš‰π™΄_𝙲𝙷𝙰𝙽𝙢𝙴, 𝙼𝙸𝙽_πš‚π™Έπš‰π™΄_π™²π™Ύπ™½πšƒπ™Έπ™½πš„π™Έπšƒπšˆ, π™Όπ™°πš‡_πš‚π™Έπš‰π™΄_π™²π™Ύπ™½πšƒπ™Έπ™½πš„π™Έπšƒπšˆ, 𝙽𝙱_𝙲𝙷𝙰𝙽𝙢𝙴, 𝙽𝙱_π™²π™Ύπ™½πšƒπ™Έπ™½πš„π™Έπšƒπšˆ, πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, π™²πšƒπš) constraint: πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› Β¬π™²πšƒπš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›. Within this expression, πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2 correspond to consecutive items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

  • πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš(π™΄πš‘πš™ 1 ,...,π™΄πš‘πš™ n )
    • πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš is a global constraint defined in the catalogue for which there exists a graph -based and/or an automaton -based representation,

    • π™΄πš‘πš™ 1 ,...,π™΄πš‘πš™ n correspond to the arguments of the global constraint πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš. Each argument should be a simple arithmetic expression that is compatible with the type declaration of the argument of πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš.

    EXAMPLE: An example of such arc constraint can be found in the definition of πšπš’πšπšπš—: πšπš’πšπšπš—(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚) uses the 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1, π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2) global constraint for defining its arc constraint. Since π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚ is a collection of type πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’-πšπšŸπšŠπš›, πšœπš’πš£-πšπšŸπšŠπš›, πšŽπš—πš-πšπšŸπšŠπš›) and since both π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1 and π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2 correspond to items of π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πš‚ there is no type compatibility problem between the call to 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™ and its definition.

  • π™°πš›πšŒπ™²πšπš› 1 π™»πš˜πšπš’πšŒπšŠπš•π™²πš˜πš—πš—πšŽπšŒπšπš˜πš› π™°πš›πšŒπ™²πšπš› 2
    • π™°πš›πšŒπ™²πšπš› 1 is an arc constraint,

    • π™»πš˜πšπš’πšŒπšŠπš•π™²πš˜πš—πš—πšŽπšŒπšπš˜πš› is one of the logical connectors ∨, ∧, β‡’, ⇔,

    • π™°πš›πšŒπ™²πšπš› 2 is an arc constraint.

    EXAMPLE: As shown by the following example, πš–πš’πš—πš’πš–πšžπš–(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) uses this kind of arc constraint: πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2βˆ¨πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›, where πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2 correspond to items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, holds if and only if one of the following conditions holds:

    • πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 and πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2 correspond to the same item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection,

    • The πšŸπšŠπš› attribute of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1 is strictly less than the πšŸπšŠπš› attribute of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.