5.167. int_value_precede_chain

DESCRIPTIONLINKSAUTOMATON
Origin

[YatChiuLawJimmyLee04]

Constraint

πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš—(πš…π™°π™»πš„π™΄πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πš’πš—πš)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš›)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Assuming n denotes the number of items of the πš…π™°π™»πš„π™΄πš‚ collection, the following condition holds for every i∈[1,n-1]: When it is defined, the first occurrence of the (i+1) th value of the πš…π™°π™»πš„π™΄πš‚ collection should be preceded by the first occurrence of the i th value of the πš…π™°π™»πš„π™΄πš‚ collection.

Example
4,0,1,4,0,6,1,0

The πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint holds since:

  • 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
|πš…π™°π™»πš„π™΄πš‚|>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
𝚞𝚜𝚎𝚍_πš‹πš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)
Symmetry

An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that does not occur in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš› can be replaced by any other value that also does not occur in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš›.

Usage

The πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint is useful for breaking symmetries in graph colouring problems. We set a πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint on all variables V 1 ,V 2 ,...,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 ,...,V n .

Figure 5.167.1 illustrates the problem of colouring earth and mars from Thom Sulanke. Part (A) of Figure 5.167.1 provides a solution where the first occurrence of each value of i, (i∈{1,2,...,8}) is located before the first occurrence of value i+1. This is obtained by using the following constraints:

𝙰≠𝙱,𝙰≠𝙴,𝙰≠𝙡,𝙰≠𝙢,𝙰≠𝙷,𝙰≠𝙸,𝙰≠𝙹,𝙰≠𝙺,𝙱≠𝙰,𝙱≠𝙲,𝙱≠𝙡,𝙱≠𝙢,𝙱≠𝙷,𝙱≠𝙸,𝙱≠𝙹,𝙱≠𝙺,𝙲≠𝙱,𝙲≠𝙳,𝙲≠𝙡,𝙲≠𝙢,𝙲≠𝙷,𝙲≠𝙸,𝙲≠𝙹,𝙲≠𝙺,𝙳≠𝙲,𝙳≠𝙴,𝙳≠𝙡,𝙳≠𝙢,𝙳≠𝙷,𝙳≠𝙸,𝙳≠𝙹,𝙳≠𝙺,𝙴≠𝙰,𝙴≠𝙳,𝙴≠𝙡,𝙴≠𝙢,𝙴≠𝙷,𝙴≠𝙸,𝙴≠𝙹,𝙴≠𝙺,𝙡≠𝙰,𝙡≠𝙱,𝙡≠𝙲,𝙡≠𝙳,𝙡≠𝙴,𝙡≠𝙢,𝙡≠𝙷,𝙡≠𝙸,𝙡≠𝙹,𝙡≠𝙺,𝙢≠𝙰,𝙢≠𝙱,𝙢≠𝙲,𝙢≠𝙳,𝙢≠𝙴,𝙢≠𝙡,𝙢≠𝙷,𝙢≠𝙸,𝙢≠𝙹,𝙢≠𝙺,𝙷≠𝙰,𝙷≠𝙱,𝙷≠𝙲,𝙷≠𝙳,𝙷≠𝙴,𝙷≠𝙡,𝙷≠𝙢,𝙷≠𝙸,𝙷≠𝙹,𝙷≠𝙺,𝙸≠𝙰,𝙸≠𝙱,𝙸≠𝙲,𝙸≠𝙳,𝙸≠𝙴,𝙸≠𝙡,𝙸≠𝙢,𝙸≠𝙷,𝙸≠𝙹,𝙸≠𝙺,𝙹≠𝙰,𝙹≠𝙱,𝙹≠𝙲,𝙹≠𝙳,𝙹≠𝙴,𝙹≠𝙡,𝙹≠𝙢,𝙹≠𝙷,𝙹≠𝙸,𝙹≠𝙺,𝙺≠𝙰,𝙺≠𝙱,𝙺≠𝙲,𝙺≠𝙳,𝙺≠𝙴,𝙺≠𝙡,𝙺≠𝙢,𝙺≠𝙷,𝙺≠𝙸,𝙺≠𝙹,πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš—(1,2,3,4,5,6,7,8,9,𝙰,𝙱,𝙲,𝙳,𝙴,𝙡,𝙢,𝙷,𝙸,𝙹,𝙺).

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

Figure 5.167.1. Using the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint for breaking symmetries in graph colouring problems
ctrs/int_value_precede_chain3
Remark

When we have more than one class of interchangeable values (i.e.,Β a partition of interchangeable values) we can use one πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— 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 πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— 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.

See also

specialisation: πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽΒ (πšœπšŽπššπšžπšŽπš—πšŒπšŽ of at least 2 πšŸπšŠπš•πšžπšŽπšœ replaced by πšœπšŽπššπšžπšŽπš—πšŒπšŽ of 2 πšŸπšŠπš•πšžπšŽπšœ).

Keywords

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

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency.

problems: graph colouring.

symmetry: symmetry, indistinguishable values, value precedence.

Automaton

FigureΒ 5.167.2 depicts the automaton associated with the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint. Let n and m respectively denote the number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection and the number of values of the πš…π™°π™»πš„π™΄πš‚ collection. Let πš…π™°πš i be the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. Let πšŸπšŠπš• v (1≀v≀m) denote the v th value of the πš…π™°π™»πš„π™΄πš‚ collection.

Figure 5.167.2. Automaton of the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint
ctrs/int_value_precede_chain1
Figure 5.167.3. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πš_πšŸπšŠπš•πšžπšŽ_πš™πš›πšŽπšŒπšŽπšπšŽ_πšŒπš‘πšŠπš’πš— constraint
ctrs/int_value_precede_chain2

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β‰₯2).

  • Let π’ž be the set of values that can be potentially assigned to a variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, but which do not belong to the values of the πš…π™°π™»πš„π™΄πš‚ collection (i.e.,Β π’ž=(π‘‘π‘œπ‘š(πš…π™°πš 1 )βˆͺπ‘‘π‘œπ‘š(πš…π™°πš 2 )βˆͺ...βˆͺπ‘‘π‘œπ‘š(πš…π™°πš n )-{πšŸπšŠπš• 1 ,πšŸπšŠπš• 2 ,...,πšŸπšŠπš• m }={w 1 ,w 2 ,...,w |π’ž| }.

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

  • We have m+1 states labelled s 0 ,s 1 ,...,s m from which s 0 is the initial state. All states are terminal states.

  • We have the following three sets of transitions:

    1. For all v∈[0,m-1], a transition from s v to s v+1 labelled by value πšŸπšŠπš• v+1 . Each transition of this type will be triggered on the first occurrence of value πšŸπšŠπš• v+1 within the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

    2. For all v∈[1,m] and for all w∈[1,v], a self loop on s v labelled by value πšŸπšŠπš• 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 π’ž is not empty, then for all v∈[0,m] a self loop on s v labelled by the fact that we take a value not in πš…π™°π™»πš„π™΄πš‚ (i.e.,Β a value in π’ž). This models the fact that, encountering a value that does not belong to the set of values of the πš…π™°π™»πš„π™΄πš‚ collection, leaves us in the same state.