5.115. elem

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š.

Constraint

๐šŽ๐š•๐šŽ๐š–(๐™ธ๐šƒ๐™ด๐™ผ,๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด)

Usual name

๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š

Synonyms

๐š—๐š๐š‘, ๐šŠ๐š›๐š›๐šŠ๐šข.

Arguments
๐™ธ๐šƒ๐™ด๐™ผ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐š๐šŽ๐šก-๐š๐šŸ๐šŠ๐š›,๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š๐šŸ๐šŠ๐š›)
๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐š๐šŽ๐šก-๐š’๐š—๐š,๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š๐šŸ๐šŠ๐š›)
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐™ธ๐šƒ๐™ด๐™ผ,[๐š’๐š—๐š๐šŽ๐šก,๐šŸ๐šŠ๐š•๐šž๐šŽ])
๐™ธ๐šƒ๐™ด๐™ผ.๐š’๐š—๐š๐šŽ๐šกโ‰ฅ1
๐™ธ๐šƒ๐™ด๐™ผ.๐š’๐š—๐š๐šŽ๐šกโ‰ค|๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด|
|๐™ธ๐šƒ๐™ด๐™ผ|=1
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด,[๐š’๐š—๐š๐šŽ๐šก,๐šŸ๐šŠ๐š•๐šž๐šŽ])
๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.๐š’๐š—๐š๐šŽ๐šกโ‰ฅ1
๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.๐š’๐š—๐š๐šŽ๐šกโ‰ค|๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด|
๐š๐š’๐šœ๐š๐š’๐š—๐šŒ๐š(๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด,๐š’๐š—๐š๐šŽ๐šก)
Purpose

๐™ธ๐šƒ๐™ด๐™ผ is equal to one of the entries of the table ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.

Example
๐š’๐š—๐š๐šŽ๐šก-3 ๐šŸ๐šŠ๐š•๐šž๐šŽ-2,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-6,๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-9,๐š’๐š—๐š๐šŽ๐šก-3๐šŸ๐šŠ๐š•๐šž๐šŽ-2,๐š’๐š—๐š๐šŽ๐šก-4๐šŸ๐šŠ๐š•๐šž๐šŽ-9

The ๐šŽ๐š•๐šŽ๐š– constraint holds since its first argument ๐™ธ๐šƒ๐™ด๐™ผ corresponds to the third item of the ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด collection.

Typical
|๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.๐šŸ๐šŠ๐š•๐šž๐šŽ)>1
Symmetries
  • Items of ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด are permutable.

  • All occurrences of two distinct values in ๐™ธ๐šƒ๐™ด๐™ผ.๐šŸ๐šŠ๐š•๐šž๐šŽ or ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.๐šŸ๐šŠ๐š•๐šž๐šŽ can be swapped; all occurrences of a value in ๐™ธ๐šƒ๐™ด๐™ผ.๐šŸ๐šŠ๐š•๐šž๐šŽ or ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.๐šŸ๐šŠ๐š•๐šž๐šŽ can be renamed to any unused value.

Usage

Makes the link between the discrete decision variable ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ and the variable ๐š…๐™ฐ๐™ป๐š„๐™ด according to a given table of values ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด. We now give five typical uses of the ๐šŽ๐š•๐šŽ๐š– constraint.

  1. In some problems we may have to represent a function y=f(x) (1โ‰คxโ‰คm). In this context we generate the following ๐šŽ๐š•๐šŽ๐š– constraint where ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ is a domain variable taking is values in {1,2,...,m}:

    ๐šŽ๐š•๐šŽ๐š–๐š’๐š—๐š๐šŽ๐šก-x๐šŸ๐šŠ๐š•๐šž๐šŽ-y,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-f(1),๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-f(2),โ‹ฎ๐š’๐š—๐š๐šŽ๐šก-m๐šŸ๐šŠ๐š•๐šž๐šŽ-f(m)
    Figure 5.115.1. y=x 3
    ctrs/elem3

    As an example, consider the problem of finding the smallest integer that can be decomposed in two different ways in the sum of two cubesย [HardyWright75]. The ๐šŽ๐š•๐šŽ๐š– constraint can be used for representing the function y=x 3 (Figureย 5.115.1). The unique solution 1729=12 3 +1 3 =10 3 +9 3 can be obtained by the following set of constraints:

    ๐šŽ๐š•๐šŽ๐š–(โŒฉ๐š’๐š—๐š๐šŽ๐šก-x 1 ๐šŸ๐šŠ๐š•๐šž๐šŽ-y 1 โŒช, โŒฉ๐š’๐š—๐š๐šŽ๐šก-1 ๐šŸ๐šŠ๐š•๐šž๐šŽ-1,๐š’๐š—๐š๐šŽ๐šก-2 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8,...,๐š’๐š—๐š๐šŽ๐šก-20 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8000โŒช)๐šŽ๐š•๐šŽ๐š–(โŒฉ๐š’๐š—๐š๐šŽ๐šก-x 2 ๐šŸ๐šŠ๐š•๐šž๐šŽ-y 2 โŒช, โŒฉ๐š’๐š—๐š๐šŽ๐šก-1 ๐šŸ๐šŠ๐š•๐šž๐šŽ-1,๐š’๐š—๐š๐šŽ๐šก-2 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8,...,๐š’๐š—๐š๐šŽ๐šก-20 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8000โŒช)๐šŽ๐š•๐šŽ๐š–(โŒฉ๐š’๐š—๐š๐šŽ๐šก-x 3 ๐šŸ๐šŠ๐š•๐šž๐šŽ-y 3 โŒช, โŒฉ๐š’๐š—๐š๐šŽ๐šก-1 ๐šŸ๐šŠ๐š•๐šž๐šŽ-1,๐š’๐š—๐š๐šŽ๐šก-2 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8,...,๐š’๐š—๐š๐šŽ๐šก-20 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8000โŒช)๐šŽ๐š•๐šŽ๐š–(โŒฉ๐š’๐š—๐š๐šŽ๐šก-x 4 ๐šŸ๐šŠ๐š•๐šž๐šŽ-y 4 โŒช, โŒฉ๐š’๐š—๐š๐šŽ๐šก-1 ๐šŸ๐šŠ๐š•๐šž๐šŽ-1,๐š’๐š—๐š๐šŽ๐šก-2 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8,...,๐š’๐š—๐š๐šŽ๐šก-20 ๐šŸ๐šŠ๐š•๐šž๐šŽ-8000โŒช)y 1 +y 2 =y 3 +y 4

  2. In some problems we need to express a disjunction of the form ๐š…๐™ฐ๐š=๐š…๐™ฐ๐š 1 โˆจ๐š…๐™ฐ๐š=๐š…๐™ฐ๐š 2 ...โˆจ๐š…๐™ฐ๐š=๐š…๐™ฐ๐š n . This can be directly reformulated as the following ๐šŽ๐š•๐šŽ๐š– constraint, where ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ is a domain variable taking its value in the finite set {1,2,...,n} and where the ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด argument corresponds to the domain variables ๐š…๐™ฐ๐š 1 ,๐š…๐™ฐ๐š 2 ,...,๐š…๐™ฐ๐š n :

    ๐šŽ๐š•๐šŽ๐š–๐š’๐š—๐š๐šŽ๐šก-๐™ธ๐™ฝ๐™ณ๐™ด๐š‡๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š…๐™ฐ๐š,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š…๐™ฐ๐š 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š…๐™ฐ๐š 2 ,โ‹ฎ๐š’๐š—๐š๐šŽ๐šก-n๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š…๐™ฐ๐š n
  3. In some scheduling problems the duration of a task depends on the machine where the task will be assigned in final schedule. In this case we generate for each task an ๐šŽ๐š•๐šŽ๐š– constraint of the following form:

    ๐šŽ๐š•๐šŽ๐š–๐š’๐š—๐š๐šŽ๐šก-๐™ผ๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐šž๐š› 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐šž๐š› 2 ,โ‹ฎ๐š’๐š—๐š๐šŽ๐šก-m๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐šž๐š› m

    where:

    • ๐™ผ๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ is a domain variable that indicates the resource to which the task will be assigned,

    • ๐™ณ๐šž๐š›๐šŠ๐š๐š’๐š˜๐š— is a domain variable that corresponds to the duration of the task,

    • ๐™ณ๐šž๐š› 1 ,๐™ณ๐šž๐š› 2 ,...,๐™ณ๐šž๐š› m are the respective duration of the task according to the hypothesis that it runs on machine 1,2 or m.

    Figure 5.115.2. A task for which the duration depends on the machine to which it is assigned
    ctrs/elem4

    Figureย 5.115.2 illustrates this particular use of the ๐šŽ๐š•๐šŽ๐š– constraint for modelling the fact that a task has a duration of 4, 6 and 4 when we respectively assign it on machines 1, 2 and 3.

  4. In some vehicle routing problems we typically use the ๐šŽ๐š•๐šŽ๐š– constraint to express the distance between the i th location and the next location visited by a vehicle. For this purpose we generate for each location i an ๐šŽ๐š•๐šŽ๐š– constraint of the form:

    ๐šŽ๐š•๐šŽ๐š–๐š’๐š—๐š๐šŽ๐šก-๐™ฝ๐šŽ๐šก๐š i ๐šŸ๐šŠ๐š•๐šž๐šŽ-๐š๐š’๐šœ๐š๐šŠ๐š—๐šŒ๐šŽ i ,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐š’๐šœ๐š i 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐š’๐šœ๐š i 2 ,โ‹ฎ๐š’๐š—๐š๐šŽ๐šก-m๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ณ๐š’๐šœ๐š i m

    where:

    • ๐™ฝ๐šŽ๐šก๐š i is a domain variable that gives the index of the location the vehicle will visit just after the i th location,

    • ๐š๐š’๐šœ๐š๐šŠ๐š—๐šŒ๐šŽ i is a domain variable that corresponds to the distance between location i and the location the vehicle will visit just after,

    • ๐™ณ๐š’๐šœ๐š i 1 ,๐™ณ๐š’๐šœ๐š i 2 ,...,๐™ณ๐š’๐šœ๐š i m are the respective distances between location i and locations 1,2,...,m.

  5. In some optimisation problems a classical use of the ๐šŽ๐š•๐šŽ๐š– constraint consists expressing the link between a discrete choice and its corresponding cost. For each discrete choice we create an ๐šŽ๐š•๐šŽ๐š– constraint of the form:

    ๐šŽ๐š•๐šŽ๐š–๐š’๐š—๐š๐šŽ๐šก-๐™ฒ๐š‘๐š˜๐š’๐šŒ๐šŽ๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ฒ๐š˜๐šœ๐š,๐š’๐š—๐š๐šŽ๐šก-1๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ฒ๐š˜๐šœ๐š 1 ,๐š’๐š—๐š๐šŽ๐šก-2๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ฒ๐š˜๐šœ๐š 2 ,โ‹ฎ๐š’๐š—๐š๐šŽ๐šก-m๐šŸ๐šŠ๐š•๐šž๐šŽ-๐™ฒ๐š˜๐šœ๐š m

    where:

    • ๐™ฒ๐š‘๐š˜๐š’๐šŒ๐šŽ is a domain variable that indicates which alternative will be finally selected,

    • ๐™ฒ๐š˜๐šœ๐š is a domain variable that corresponds to the cost of the decision associated with the value of the ๐™ฒ๐š‘๐š˜๐š’๐šŒ๐šŽ variable,

    • ๐™ฒ๐š˜๐šœ๐š 1 ,๐™ฒ๐š˜๐šœ๐š 2 ,...,๐™ฒ๐š˜๐šœ๐š m are the respective costs associated with the alternatives 1,2,...,m.

An other example where the table argument corresponds to domain variables is described in the keyword entry assignment to the same set of values.

Remark

Originally, the parameters of the ๐šŽ๐š•๐šŽ๐š– constraint had the form ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(๐™ธ๐™ฝ๐™ณ๐™ด๐š‡,๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด,๐š…๐™ฐ๐™ป๐š„๐™ด), where ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ and ๐š…๐™ฐ๐™ป๐š„๐™ด were two domain variables and ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด a list of non-negative integers.

Systems

nth in Choco, element in Gecode, element in JaCoP, element in SICStus.

See also

common keyword: ๐šŽ๐š•๐šŽ๐š–_๐š๐š›๐š˜๐š–_๐š๐š˜, ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š_๐š–๐šŠ๐š๐š›๐š’๐šก, ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š_๐š™๐š›๐š˜๐š๐šž๐šŒ๐š, ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š_๐šœ๐š™๐šŠ๐š›๐šœ๐šŽย (array constraint), ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š๐šœ_๐šœ๐š™๐šŠ๐š›๐šœ๐šŽ, ๐šœ๐š๐šŠ๐š๐šŽ_๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐šย (data constraint).

implied by: ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š.

implies: ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐šย (single item replaced by two variables), ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š_๐š๐š›๐šŽ๐šŠ๐š๐šŽ๐š›๐šŽ๐šš, ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š_๐š•๐šŽ๐šœ๐šœ๐šŽ๐šš.

system of constraints: ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š๐šœ.

uses in its reformulation: ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š๐šœ_๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š.

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: centered cyclic(2) constraint network(1).

constraint type: data constraint.

filtering: arc-consistency.

modelling: array constraint, table, functional dependency, variable indexing, variable subscript, disjunction, assignment to the same set of values, sequence dependent set-up.

modelling exercises: assignment to the same set of values, sequence dependent set-up.

Arc input(s)

๐™ธ๐šƒ๐™ด๐™ผ ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด

Arc generator
๐‘ƒ๐‘…๐‘‚๐ท๐‘ˆ๐ถ๐‘‡โ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š๐šŽ๐š–,๐š๐šŠ๐š‹๐š•๐šŽ)

Arc arity
Arc constraint(s)
โ€ข ๐š’๐š๐šŽ๐š–.๐š’๐š—๐š๐šŽ๐šก=๐š๐šŠ๐š‹๐š•๐šŽ.๐š’๐š—๐š๐šŽ๐šก
โ€ข ๐š’๐š๐šŽ๐š–.๐šŸ๐šŠ๐š•๐šž๐šŽ=๐š๐šŠ๐š‹๐š•๐šŽ.๐šŸ๐šŠ๐š•๐šž๐šŽ
Graph property(ies)
๐๐€๐‘๐‚=1

Graph model

We regroup the ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ and ๐š…๐™ฐ๐™ป๐š„๐™ด parameters of the original ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(๐™ธ๐™ฝ๐™ณ๐™ด๐š‡,๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด,๐š…๐™ฐ๐™ป๐š„๐™ด) into the parameter ๐™ธ๐šƒ๐™ด๐™ผ. We also make explicit the different indices of the table ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด.

Partsย (A) andย (B) of Figureย 5.115.3 respectively show the initial and final graph associated with the Example slot. Since we use the ๐๐€๐‘๐‚ graph property, the unique arc of the final graph is stressed in bold.

Figure 5.115.3. Initial and final graph of the ๐šŽ๐š•๐šŽ๐š– constraint
ctrs/elemActrs/elemB
(a) (b)
Signature

Since all the ๐š’๐š—๐š๐šŽ๐šก attributes of ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด are distinct and because of the first condition of the arc constraint the final graph cannot have more than one arc. Therefore we can rewrite ๐๐€๐‘๐‚=1 to ๐๐€๐‘๐‚โ‰ฅ1 and simplify ๐๐€๐‘๐‚ ยฏ ฬฒ to ๐๐€๐‘๐‚ ยฏ.

Automaton

Figureย 5.115.4 depicts the automaton associated with the ๐šŽ๐š•๐šŽ๐š– constraint. Let ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ and ๐š…๐™ฐ๐™ป๐š„๐™ด respectively be the ๐š’๐š—๐š๐šŽ๐šก and the ๐šŸ๐šŠ๐š•๐šž๐šŽ attributes of the unique item of the ๐™ธ๐šƒ๐™ด๐™ผ collection. Let ๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ i and ๐š…๐™ฐ๐™ป๐š„๐™ด i respectively be the ๐š’๐š—๐š๐šŽ๐šก and the ๐šŸ๐šŠ๐š•๐šž๐šŽ attributes of the i th item of the ๐šƒ๐™ฐ๐™ฑ๐™ป๐™ด collection. To each quadruple (๐™ธ๐™ฝ๐™ณ๐™ด๐š‡,๐š…๐™ฐ๐™ป๐š„๐™ด,๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ i ,๐š…๐™ฐ๐™ป๐š„๐™ด i ) corresponds a 0-1 signature variable ๐š‚ i as well as the following signature constraint: ((๐™ธ๐™ฝ๐™ณ๐™ด๐š‡=๐™ธ๐™ฝ๐™ณ๐™ด๐š‡ i )โˆง(๐š…๐™ฐ๐™ป๐š„๐™ด=๐š…๐™ฐ๐™ป๐š„๐™ด i ))โ‡”๐š‚ i .

Figure 5.115.4. Automaton of the ๐šŽ๐š•๐šŽ๐š– constraint
ctrs/elem1
Figure 5.115.5. Hypergraph of the reformulation corresponding to the automaton of the ๐šŽ๐š•๐šŽ๐š– constraint
ctrs/elem2