## 5.114. domain_constraint

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$

Synonym

$\mathrm{\pi \pi \pi \pi \pi \pi }$.

Arguments
 $\mathrm{\pi  \pi °\pi }$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }\mathtt{01}-\mathrm{\pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\left[\mathrm{\pi \pi \pi }\mathtt{01},\mathrm{\pi \pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }\mathtt{01}\beta ₯0$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }\mathtt{01}\beta €1$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi \pi \pi }\right)$
Purpose

Make the link between a domain variable $\mathrm{\pi  \pi °\pi }$ and those 0-1 variables that are associated with each potential value of $\mathrm{\pi  \pi °\pi }$: The 0-1 variable associated with the value that is taken by variable $\mathrm{\pi  \pi °\pi }$ is equal to 1, while the remaining 0-1 variables are all equal to 0.

Example
$\left(\begin{array}{c}5,β©\begin{array}{cc}\mathrm{\pi \pi \pi }\mathtt{01}-0\hfill & \mathrm{\pi \pi \pi \pi \pi }-9,\hfill \\ \mathrm{\pi \pi \pi }\mathtt{01}-1\hfill & \mathrm{\pi \pi \pi \pi \pi }-5,\hfill \\ \mathrm{\pi \pi \pi }\mathtt{01}-0\hfill & \mathrm{\pi \pi \pi \pi \pi }-2,\hfill \\ \mathrm{\pi \pi \pi }\mathtt{01}-0\hfill & \mathrm{\pi \pi \pi \pi \pi }-7\hfill \end{array}βͺ\hfill \end{array}\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ holds since $\mathrm{\pi  \pi °\pi }=5$ is set to the value corresponding to the 0-1 variable set to 1, while the other 0-1 variables are all set to 0.

Typical
$|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|>1$
Symmetry

Items of $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ are permutable.

Usage

This constraint is used in order to make the link between a formulation using finite domain constraints and a formulation exploiting 0-1 variables.

Reformulation

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi },$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\beta ©\mathrm{\pi \pi \pi }\mathtt{01}-{B}_{1}\mathrm{\pi \pi \pi \pi \pi }-{v}_{1},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }\mathtt{01}-{B}_{2}\mathrm{\pi \pi \pi \pi \pi }-{v}_{2},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $........................$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }\mathtt{01}-{B}_{|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|}\mathrm{\pi \pi \pi \pi \pi }-{v}_{|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|}\beta ͺ\right)$

constraint can be expressed in term of the following reified constraint $\left(\mathrm{\pi  \pi °\pi }={v}_{1}\beta §{B}_{1}=1\right)\beta ¨\left(\mathrm{\pi  \pi °\pi }={v}_{2}\beta §{B}_{2}=1\right)\beta ¨...\beta ¨\left(\mathrm{\pi  \pi °\pi }={v}_{|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|}\beta §{B}_{|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|}=1\right)$.

Systems
Keywords
Derived Collection
$\mathrm{\pi \pi \pi }\left(\begin{array}{c}\mathrm{\pi  \pi °\pi »\pi \pi ΄}-\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }\mathtt{01}-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right),\hfill \\ \mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }\mathtt{01}-1,\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi  \pi °\pi }\right)\right]\hfill \end{array}\right)$
Arc input(s)

$\mathrm{\pi  \pi °\pi »\pi \pi ΄}$ $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$

Arc generator
$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi },\mathrm{\pi \pi \pi \pi \pi \pi }\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi \pi \pi }\beta \mathrm{\pi \pi \pi \pi \pi \pi }.\mathrm{\pi \pi \pi }\mathtt{01}=1$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$

Graph model

The $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint is modelled with the following bipartite graph:

• The first class of vertices corresponds to one single vertex containing the domain variable.

• The second class of vertices contains one vertex for each item of the collection $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$.

$\mathrm{\pi \pi  \pi \pi ·\pi \pi Ά\pi }$ is used in order to generate the arcs of the graph. In our context it takes a collection with one single item $\beta ©\mathrm{\pi \pi \pi }\mathtt{01}-1\mathrm{\pi \pi \pi \pi \pi }-\mathrm{\pi  \pi °\pi }\beta ͺ$ and the collection $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$.

The arc constraint between the variable $\mathrm{\pi  \pi °\pi }$ and one potential value $v$ expresses the following:

• If the 0-1 variable associated with $v$ is equal to 1, $\mathrm{\pi  \pi °\pi }$ is equal to $v$.

• Otherwise, if the 0-1 variable associated with $v$ is equal to 0, $\mathrm{\pi  \pi °\pi }$ is not equal to $v$.

Since all arc constraints should hold the final graph contains exactly $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$ arcs.

PartsΒ (A) andΒ (B) of FigureΒ 5.114.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ graph property, the arcs of the final graph are stressed in bold.

Signature

Since the number of arcs of the initial graph is equal to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ the maximum number of arcs of the final graph is also equal to $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$. Therefore we can rewrite the graph property $\mathrm{\pi \pi \pi \pi }$ $=$ $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$ to $\mathrm{\pi \pi \pi \pi }$ $\beta ₯$ $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$. This leads to simplify $\underset{Μ²}{\stackrel{Β―}{\mathrm{\pi \pi \pi \pi }}}$ to $\stackrel{Β―}{\mathrm{\pi \pi \pi \pi }}$.

Automaton

FigureΒ 5.114.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. Let $\mathrm{\pi  \pi °\pi }{\mathtt{01}}_{i}$ and ${\mathrm{\pi  \pi °\pi »\pi \pi ΄}}_{i}$ respectively be the $\mathrm{\pi \pi \pi }\mathtt{01}$ and the $\mathrm{\pi \pi \pi \pi \pi }$ attributes of the ${i}^{th}$ item of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection. To each triple $\left(\mathrm{\pi  \pi °\pi },\mathrm{\pi  \pi °\pi }{\mathtt{01}}_{i},{\mathrm{\pi  \pi °\pi »\pi \pi ΄}}_{i}\right)$ corresponds a 0-1 signature variable ${\mathrm{\pi }}_{i}$ as well as the following signature constraint: $\left(\left(\mathrm{\pi  \pi °\pi }={\mathrm{\pi  \pi °\pi »\pi \pi ΄}}_{i}\right)\beta \mathrm{\pi  \pi °\pi }{\mathtt{01}}_{i}\right)\beta {\mathrm{\pi }}_{i}$.