5.196. int_value_precede_chain

Origin
Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$.

Arguments
 $\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 }\right)$ $\mathrm{\pi  \pi °\pi \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 }\right)$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

Assuming $n$ denotes the number of items of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection, the following condition holds for every $i\beta \left[1,n-1\right]$: When it is defined, the first occurrence of the ${\left(i+1\right)}^{th}$ value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection should be preceded by the first occurrence of the ${i}^{th}$ value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection.

Example
$\left(β©4,0,1βͺ,β©4,0,6,1,0βͺ\right)$

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraint holds since within the sequence 4, 0, 6, 1, 0:

• The first occurrence of value 4 occurs before the first occurrence of value 0.

• The first occurrence of value 0 occurs before the first occurrence of value 1.

Typical
 $|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi ’}_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>|\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$ $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi ’}$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\right)$
Symmetry

An occurrence of a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that does not occur in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$ can be replaced by any other value that also does not occur in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }.\mathrm{\pi \pi \pi }$.

Arg. properties
• Contractible wrt. $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$.

• Suffix-contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

• Aggregate: $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }\left(\mathrm{\pi \pi }\right)$, $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\left(\mathrm{\pi \pi \pi \pi \pi }\right)$.

Usage

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraint is useful for breaking symmetries in graph colouring problems. We set a $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraint on all variables ${V}_{1},{V}_{2},\beta ―,{V}_{n}$ associated with the vertices of the graph to colour, where we state that the first occurrence of colour $i$ should be located before the first occurrence of colour $i+1$ within the sequence ${V}_{1},{V}_{2},\beta ―,{V}_{n}$.

FigureΒ 5.196.1 illustrates the problem of colouring earth and mars from Thom Sulanke. PartΒ (A) of FigureΒ 5.196.1 provides a solution where the first occurrence of each value of $i$, $\left(i\beta \left\{1,2,\beta ―,8\right\}\right)$ is located before the first occurrence of value $i+1$. This is obtained by using the following constraints:

PartΒ (B) provides a symmetric solution where the value precedence constraints between the pairs of values $\left(1,2\right)$, $\left(2,3\right)$, $\left(4,5\right)$, $\left(7,8\right)$ and $\left(8,9\right)$ are all violated (each violation is depicted by a dashed arc).

Remark

When we have more than one class of interchangeable values (i.e.,Β a partition of interchangeable values) we can use one $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraint for breaking value symmetry in each class of interchangeable values. However it was shown inΒ [Walsh07] that enforcing arc-consistency for such a conjunction of $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraints is NP-hard.

Algorithm

The 2004 reformulationΒ [Beldiceanu04] associated with the automaton of the Automaton slot achieves arc-consistency since the corresponding constraint network is a Berge-acyclic constraint network. Later on, another formulation into a sequence of ternary sliding constraints was proposed byΒ [Walsh06]. It also achieves arc-consistency for the same reason.

Systems

specialisation: $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ of at least 2 $\mathrm{\pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ of 2 $\mathrm{\pi \pi \pi \pi \pi \pi }$).

Keywords
Automaton

FigureΒ 5.196.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ constraint. Let $n$ and $m$ respectively denote the number of variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection and the number of values of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection. Let ${\mathrm{\pi  \pi °\pi }}_{i}$ be the ${i}^{th}$ variable of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. Let ${\mathrm{\pi \pi \pi }}_{v}$ $\left(1\beta €v\beta €m\right)$ denote the ${v}^{th}$ value of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection.

We now show how to construct such an automaton systematically. For this purpose let us first introduce some notations:

• Without loss of generality we assume that we have at least two values (i.e.,Β $m\beta ₯2$).

• Let $\mathrm{\pi }$ be the set of values that can be potentially assigned to a variable of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection, but which do not belong to the values of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection (i.e.,Β $\mathrm{\pi }=\left(\mathrm{\pi \pi \pi }\left({\mathrm{\pi  \pi °\pi }}_{1}\right)\beta ͺ\mathrm{\pi \pi \pi }\left({\mathrm{\pi  \pi °\pi }}_{2}\right)\beta ͺ\beta ―\beta ͺ\mathrm{\pi \pi \pi }\left({\mathrm{\pi  \pi °\pi }}_{n}\right)-\left\{{\mathrm{\pi \pi \pi }}_{1},{\mathrm{\pi \pi \pi }}_{2},\beta ―,{\mathrm{\pi \pi \pi }}_{m}\right\}=\left\{{w}_{1},{w}_{2},\beta ―,{w}_{|\mathrm{\pi }|}\right\}$.

The states and transitions of the automaton are respectively defined in the following way:

• We have $m+1$ states labelled ${s}_{0},{s}_{1},\beta ―,{s}_{m}$ from which ${s}_{0}$ is the initial state. All states are accepting states.

• We have the following three sets of transitions:

1. For all $v\beta \left[0,m-1\right]$, a transition from ${s}_{v}$ to ${s}_{v+1}$ labelled by value ${\mathrm{\pi \pi \pi }}_{v+1}$. Each transition of this type will be triggered on the first occurrence of value ${\mathrm{\pi \pi \pi }}_{v+1}$ within the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

2. For all $v\beta \left[1,m\right]$ and for all $w\beta \left[1,v\right]$, a self loop on ${s}_{v}$ labelled by value ${\mathrm{\pi \pi \pi }}_{w}$. Such transitions encode the fact that we stay in the same state as long as we have a value that was already encountered.

3. If the set $\mathrm{\pi }$ is not empty, then for all $v\beta \left[0,m\right]$ a self loop on ${s}_{v}$ labelled by the fact that we take a value not in $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ (i.e.,Β a value in $\mathrm{\pi }$). This models the fact that, encountering a value that does not belong to the set of values of the $\mathrm{\pi  \pi °\pi »\pi \pi ΄\pi }$ collection, leaves us in the same state.