Derived from $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$.

$\mathrm{𝚎𝚕𝚎𝚖}(\mathrm{𝙸𝚃𝙴𝙼},\mathrm{𝚃𝙰𝙱𝙻𝙴})$

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$

$\mathrm{𝚗𝚝𝚑}$, $\mathrm{𝚊𝚛𝚛𝚊𝚢}$.

The $\mathrm{𝚎𝚕𝚎𝚖}$ constraint holds since its first argument $\mathrm{𝙸𝚃𝙴𝙼}$ corresponds to the third item of the $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ collection.

• Items of $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ are permutable.

• All occurrences of two distinct values in $\mathrm{𝙸𝚃𝙴𝙼}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$ or $\mathrm{𝚃𝙰𝙱𝙻𝙴}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$ can be swapped; all occurrences of a value in $\mathrm{𝙸𝚃𝙴𝙼}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$ or $\mathrm{𝚃𝙰𝙱𝙻𝙴}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$ can be renamed to any unused value.

Functional dependency: $\mathrm{𝙸𝚃𝙴𝙼}.\mathrm{𝚟𝚊𝚕𝚞𝚎}$ determined by $\mathrm{𝙸𝚃𝙴𝙼}.\mathrm{𝚒𝚗𝚍𝚎𝚡}$ and $\mathrm{𝚃𝙰𝙱𝙻𝙴}$.

Makes the link between the discrete decision variable $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ and the variable $\mathrm{𝚅𝙰𝙻𝚄𝙴}$ according to a given table of values $\mathrm{𝚃𝙰𝙱𝙻𝙴}$. We now give five typical uses of the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint.

1. In some problems we may have to represent a function $y=f\left(x\right)$ (with $x\in [1,m]$). In this context we generate the following $\mathrm{𝚎𝚕𝚎𝚖}$ constraint where $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ is a domain variable taking its values in $\{1,2,\cdots ,m\}$:

   $$\mathrm{𝚎𝚕𝚎𝚖}\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-x\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-y\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-f\left(1\right),\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-f\left(2\right),\hfill \\ & ⋮\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-m\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-f\left(m\right)\hfill \end{array}〉\hfill \end{array}\right)$$

   Figure 5.137.1. $y=x^3$ ($1\le x\le 3$)

   

   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 $\mathrm{𝚎𝚕𝚎𝚖}$ constraint can be used for representing the function $y=x^3$ (Figure 5.137.1). The unique solution $1729={12}^3+1^3={10}^3+9^3$ can be obtained by the following set of constraints:

   $\left\{\begin{array}{c}\mathrm{𝚎𝚕𝚎𝚖}(\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-x_1\mathrm{𝚟𝚊𝚕𝚞𝚎}-y_1\rangle ,\hfill \\ \langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-1\mathrm{𝚟𝚊𝚕𝚞𝚎}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-2\mathrm{𝚟𝚊𝚕𝚞𝚎}-8,\cdots ,\mathrm{𝚒𝚗𝚍𝚎𝚡}-20\mathrm{𝚟𝚊𝚕𝚞𝚎}-8000\rangle )\hfill \\ \mathrm{𝚎𝚕𝚎𝚖}(\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-x_2\mathrm{𝚟𝚊𝚕𝚞𝚎}-y_2\rangle ,\hfill \\ \langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-1\mathrm{𝚟𝚊𝚕𝚞𝚎}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-2\mathrm{𝚟𝚊𝚕𝚞𝚎}-8,\cdots ,\mathrm{𝚒𝚗𝚍𝚎𝚡}-20\mathrm{𝚟𝚊𝚕𝚞𝚎}-8000\rangle )\hfill \\ \mathrm{𝚎𝚕𝚎𝚖}(\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-x_3\mathrm{𝚟𝚊𝚕𝚞𝚎}-y_3\rangle ,\hfill \\ \langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-1\mathrm{𝚟𝚊𝚕𝚞𝚎}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-2\mathrm{𝚟𝚊𝚕𝚞𝚎}-8,\cdots ,\mathrm{𝚒𝚗𝚍𝚎𝚡}-20\mathrm{𝚟𝚊𝚕𝚞𝚎}-8000\rangle )\hfill \\ \mathrm{𝚎𝚕𝚎𝚖}(\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-x_4\mathrm{𝚟𝚊𝚕𝚞𝚎}-y_4\rangle ,\hfill \\ \langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-1\mathrm{𝚟𝚊𝚕𝚞𝚎}-1,\mathrm{𝚒𝚗𝚍𝚎𝚡}-2\mathrm{𝚟𝚊𝚕𝚞𝚎}-8,\cdots ,\mathrm{𝚒𝚗𝚍𝚎𝚡}-20\mathrm{𝚟𝚊𝚕𝚞𝚎}-8000\rangle )\hfill \\ y_1+y_2=y_3+y_4\hfill \\ x_1<x_2\hfill \\ x_3<x_4\hfill \\ x_1<x_3\hfill \end{array}\right.$ The last three inequalities constraints in the conjunction are used for breaking symmetries. The constraints $x_1<x_2$ and $x_3<x_4$ respectively order the pairs of variables $(x_1,x_2)$ and $(x_3,x_4)$ from which the sums $x_1^3+x_2^3$ and $x_3^3+x_4^3$ are generated. Finally the inequality $x_1<x_3$ enforces a lexicographic ordering between the two pairs of variables $(x_1,x_2)$ and $(x_3,x_4)$.

2. In some optimisation problems a classical use of the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint consists expressing the link between a discrete choice and its corresponding cost. For each discrete choice we create an $\mathrm{𝚎𝚕𝚎𝚖}$ constraint of the form:

   $$\mathrm{𝚎𝚕𝚎𝚖}\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝙲𝚑𝚘𝚒𝚌𝚎}\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝙲𝚘𝚜𝚝}\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙲𝚘𝚜𝚝}}_1,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙲𝚘𝚜𝚝}}_2,\hfill \\ & ⋮\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-m\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙲𝚘𝚜𝚝}}_m\hfill \end{array}〉\hfill \end{array}\right)$$

   where:

   • $\mathrm{𝙲𝚑𝚘𝚒𝚌𝚎}$ is a domain variable that indicates which alternative will be finally selected,

   • $\mathrm{𝙲𝚘𝚜𝚝}$ is a domain variable that corresponds to the cost of the decision associated with the value of the $\mathrm{𝙲𝚑𝚘𝚒𝚌𝚎}$ variable,

   • ${\mathrm{𝙲𝚘𝚜𝚝}}_1,{\mathrm{𝙲𝚘𝚜𝚝}}_2,\cdots ,{\mathrm{𝙲𝚘𝚜𝚝}}_m$ are the respective costs associated with the alternatives $1,2,\cdots ,m$.

3. In some problems we need to express a disjunction of the form $\mathrm{𝚅𝙰𝚁}={\mathrm{𝚅𝙰𝚁}}_1\vee \mathrm{𝚅𝙰𝚁}={\mathrm{𝚅𝙰𝚁}}_2\vee \cdots \vee \mathrm{𝚅𝙰𝚁}={\mathrm{𝚅𝙰𝚁}}_n$. This can be directly reformulated as the following $\mathrm{𝚎𝚕𝚎𝚖}$ constraint, where $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ is a domain variable taking its value in the finite set $\{1,2,\cdots ,n\}$ and where the $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ argument corresponds to the domain variables ${\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,\cdots ,{\mathrm{𝚅𝙰𝚁}}_n$:

   $$\mathrm{𝚎𝚕𝚎𝚖}\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝙸𝙽𝙳𝙴𝚇}\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝚅𝙰𝚁}\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝚅𝙰𝚁}}_1,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝚅𝙰𝚁}}_2,\hfill \\ & ⋮\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-n\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝚅𝙰𝚁}}_n\hfill \end{array}〉\hfill \end{array}\right)$$

4. 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 $\mathrm{𝚎𝚕𝚎𝚖}$ constraint of the following form:

   $$\mathrm{𝚎𝚕𝚎𝚖}\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝙼𝚊𝚌𝚑𝚒𝚗𝚎}\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-\mathrm{𝙳𝚞𝚛𝚊𝚝𝚒𝚘𝚗}\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚞𝚛}}_1,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚞𝚛}}_2,\hfill \\ & ⋮\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-m\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚞𝚛}}_m\hfill \end{array}〉\hfill \end{array}\right)$$

   where:

   • $\mathrm{𝙼𝚊𝚌𝚑𝚒𝚗𝚎}$ is a domain variable that indicates the resource to which the task will be assigned,

   • $\mathrm{𝙳𝚞𝚛𝚊𝚝𝚒𝚘𝚗}$ is a domain variable that corresponds to the duration of the task,

   • ${\mathrm{𝙳𝚞𝚛}}_1,{\mathrm{𝙳𝚞𝚛}}_2,\cdots ,{\mathrm{𝙳𝚞𝚛}}_m$ are the respective duration of the task according to the hypothesis that it runs on machine $1,2$ or $m$.

   Figure 5.137.2. A task $t$ for which the duration depends on the machine 1, 2 or 3 to which it is assigned

   

   Figure 5.137.2 illustrates this particular use of the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint for modelling that a task has a duration of 4, 6 and 4 when we respectively assign it on machines 1, 2 and 3.

5. In some vehicle routing problems we typically use the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint to express the distance between location $i$ and the next location visited by a vehicle. For this purpose we generate for each location $i$ an $\mathrm{𝚎𝚕𝚎𝚖}$ constraint of the form:

   $$\mathrm{𝚎𝚕𝚎𝚖}\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-{\mathrm{𝙽𝚎𝚡𝚝}}_i\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}}_i\hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚒𝚜𝚝}}_{i_1},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚒𝚜𝚝}}_{i_2},\hfill \\ & ⋮\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-m\hfill & \mathrm{𝚟𝚊𝚕𝚞𝚎}-{\mathrm{𝙳𝚒𝚜𝚝}}_{i_m}\hfill \end{array}〉\hfill \end{array}\right)$$

   where:

   • ${\mathrm{𝙽𝚎𝚡𝚝}}_i$ is a domain variable that gives the index of the location the vehicle will visit just after location $i$,

   • ${\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}}_i$ is a domain variable that corresponds to the distance between location $i$ and the location the vehicle will visit just after,

   • ${\mathrm{𝙳𝚒𝚜𝚝}}_{i_1},{\mathrm{𝙳𝚒𝚜𝚝}}_{i_2},\cdots ,{\mathrm{𝙳𝚒𝚜𝚝}}_{i_m}$ are the respective distances between location $i$ and locations $1,2,\cdots ,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.

Originally, the parameters of the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint had the form $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}(\mathrm{𝙸𝙽𝙳𝙴𝚇},\mathrm{𝚃𝙰𝙱𝙻𝙴},\mathrm{𝚅𝙰𝙻𝚄𝙴})$, where $\mathrm{𝙸𝙽𝙳𝙴𝚇}$ and $\mathrm{𝚅𝙰𝙻𝚄𝙴}$ were two domain variables and $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ was a list of non-negative integers.

Within some systems (e.g., Gecode), the index of the first entry of the table $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ corresponds to 0 rather than to 1.

When the first entry of the table $\mathrm{𝚃𝙰𝙱𝙻𝙴}$ corresponds to a value $p$ that is different from 1 we can still use the $\mathrm{𝚎𝚕𝚎𝚖}$ constraint. We use the reformulation $I=J-p+1$ $\wedge$ $\mathrm{𝚎𝚕𝚎𝚖}(\langle \mathrm{𝚒𝚗𝚍𝚎𝚡}-I\mathrm{𝚟𝚊𝚕𝚞𝚎}-V\rangle ,\mathrm{𝚃𝙰𝙱𝙻𝙴})$, where $I$ and $J$ are domain variables respectively ranging from 1 to $\left|\mathrm{𝚃𝙰𝙱𝙻𝙴}\right|$ and from $p$ to $p+\left|\mathrm{𝚃𝙰𝙱𝙻𝙴}\right|-1$.

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

common keyword: $\mathrm{𝚎𝚕𝚎𝚖}\_\mathrm{𝚏𝚛𝚘𝚖}\_\mathrm{𝚝𝚘}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\_\mathrm{𝚜𝚙𝚊𝚛𝚜𝚎}$ (array constraint), $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜}\_\mathrm{𝚜𝚙𝚊𝚛𝚜𝚎}$, $\mathrm{𝚜𝚝𝚊𝚐𝚎}\_\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ (data constraint).

implied by: $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$.

implies: $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ (single item replaced by two variables), $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\_\mathrm{𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}\_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜}$.

system of constraints: $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜}$.

uses in its reformulation: $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$.

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

constraint arguments: pure functional dependency.

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

constraint type: data constraint.

filtering: arc-consistency.

heuristics: labelling by increasing cost, regret based heuristics.

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, zebra puzzle.

puzzles: zebra puzzle.