5.160. increasing_global_cardinality

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Conjoin πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ and πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

Constraint

πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Synonyms

πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚐𝚌𝚌, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚐𝚌𝚌_πš•πš˜πš _πšžπš™.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš,πš˜πš–πš’πš—-πš’πš—πš,πš˜πš–πšŠπš‘-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
|πš…π™°π™»πš„π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš•,πš˜πš–πš’πš—,πš˜πš–πšŠπš‘])
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰₯0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰€πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘
Purpose

The variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are increasing. In addition, each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (1≀i≀|πš…π™°π™»πš„π™΄πš‚|) should be taken by at least πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πš’πš— and at most πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

Example
3,3,6,8,πšŸπšŠπš•-3πš˜πš–πš’πš—-2πš˜πš–πšŠπš‘-3,πšŸπšŠπš•-5πš˜πš–πš’πš—-0πš˜πš–πšŠπš‘-1,πšŸπšŠπš•-6πš˜πš–πš’πš—-1πš˜πš–πšŠπš‘-2

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint holds since:

  • The values of the collection 〈3,3,6,8βŒͺ are sorted in increasing order.

  • Values 3, 5 and 6 are respectively used 2 (2≀2≀3), 0 (0≀0≀1) and 1 (1≀1≀2) times within the collection 〈3,3,6,8βŒͺ and since no constraint was specified for value 8.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°π™»πš„π™΄πš‚|>1
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘>0
πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetry

Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

Usage

This constraint can be used in order to break symmetry in the context of the following pattern. We have a matrix β„³ of variables with the same constraint on each row and a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint on each column. Beside lexicographically ordering the rows of β„³ with a πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraint, one can also state a πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ on the first column of β„³ in order to improve propagation on the corresponding variables.

Reformulation

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint can be expressed in term of a conjunction of a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ and an πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraints. Even if we achieve arc-consistency on these two constraints this hinders propagation as shown by the following small example.

We have two variables X and Y (X≀Y), which both take their values in the set {2,3}. In addition, assume that the minimum number of occurrences of values 0, 1 and 2 are respectively equal to 0, 1 and 1. Similarly assume that, the maximum number of occurrences of values 0, 1 and 2 are respectively equal to 1, 1 and 2. The reformulation does not reduce the domain of variables X, Y in any way, while the automaton described in the Automaton slot fixes X to 2 and Y to 3.

See also

implies: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

related: πš˜πš›πšπšŽπš›πšŽπš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Keywords

application area: assignment.

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

constraint network structure: Berge-acyclic constraint network.

constraint type: value constraint, order constraint.

filtering: arc-consistency.

symmetry: symmetry, matrix symmetry.

For all items of πš…π™°π™»πš„π™΄πš‚:

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•
Graph property(ies)
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš—
β€’ ππ•π„π‘π“π„π—β‰€πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘

Graph model

Since we want to express one unary constraint for each value we use the β€œFor all items of πš…π™°π™»πš„π™΄πš‚β€ iterator. PartΒ (A) of FigureΒ 5.160.1 shows the initial graphs associated with each value 3, 5 and 6 of the πš…π™°π™»πš„π™΄πš‚ collection of the Example slot. PartΒ (B) of FigureΒ 5.160.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection (since value 5 is not assigned to any variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection the final graph associated with value 5 is empty). Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graphs are stressed in bold.

Figure 5.160.1. Initial and final graph of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint
ctrs/increasing_global_cardinalityActrs/increasing_global_cardinalityB
(a) (b)
Automaton

A first systematic approach for creating an automaton that only recognises the solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint could be to:

However this approach is not going to scale well in practice since the automaton associated with the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint may have a too big size. Therefore we propose an approach where we directly construct in one single step the automaton that only recognises the solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint. Note that we do not have any formal proof that the resulting automaton is always minimum.

Without loss of generality, we assume that:

  • All items of the πš…π™°π™»πš„π™΄πš‚ collection are sorted in increasing value on the attribute πšŸπšŠπš•.

  • All the potential values of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection are included within the set of values of the collection πš…π™°π™»πš„π™΄πš‚ (i.e.,Β the πšŸπšŠπš• attribute).If this is not the case, we can include these values within the πš…π™°π™»πš„π™΄πš‚ collection and set their minimum and maximum number of occurrences to 0 and |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-βˆ‘ v=1 |πš…π™°π™»πš„π™΄πš‚| πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—.

Before defining the states of the automaton, we first need to introduce the following notion. A value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• is constrained by its maximum number of occurrences if and only if πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘β‰€1βˆ¨πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-βˆ‘ u=1,uβ‰ v |πš…π™°π™»πš„π™΄πš‚| πš…π™°π™»πš„π™΄πš‚[u].πš˜πš–πš’πš—.When πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘β‰€1 we cannot reduce the number of states related to value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• and we therefore consider that we are in the constrained case. Let 𝒱 denote the set of constrained values (i.e.,Β their indexes within the collection πš…π™°π™»πš„π™΄πš‚) by their respective maximum number of occurrences.

After determining the set 𝒱, the πš˜πš–πšŠπš‘ attribute of each potential value is normalised in the following way:

  • For an unconstrained value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• we reset πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘ to max(1,πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—).

  • For a constrained value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• we reset πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘ to 1 if its current value is smaller than 1.

We are now in position to introduce the states of the automaton.

The 1+βˆ‘ v=1,vβˆˆπ’± |πš…π™°π™»πš„π™΄πš‚| πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘+βˆ‘ v=1,vβˆ‰π’± |πš…π™°π™»πš„π™΄πš‚| πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš— states of the automaton that only accepts solutions of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint are defined in the following way:

  • For the v π‘‘β„Ž item of the collection πš…π™°π™»πš„π™΄πš‚ we have:

    • If vβˆˆπ’±, πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘ states labelled by s vo (1≀oβ‰€πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘).

    • If vβˆ‰π’±, πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš— states labelled by s vo (1≀oβ‰€πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—).

  • We have an initial state labelled by s 00 .

Terminal states correspond to those states s vo such that, both (1)Β o is greater than or equal to πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—, and (2)Β there is no value item πš…π™°π™»πš„π™΄πš‚[w] (w>v) such that πš…π™°π™»πš„π™΄πš‚[w].πš˜πš–πš’πš—>0. Transitions are defined in the following way:

  • There is an arc, labelled by πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš•, from the initial state s 00 to every state s v1 where πš…π™°π™»πš„π™΄πš‚[v] is an item for which all values πš…π™°π™»πš„π™΄πš‚[u].πšŸπšŠπš• strictly less than πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• verify the condition πš…π™°π™»πš„π™΄πš‚[u].πš˜πš–πš’πš—=0.

  • For each value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• constrained by its maximum number of occurrences (i.e.,Β vβˆˆπ’±), there is an arc, labelled by πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš•, from the state s vk to the state s vk+1 for all k in [1,πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘-1].

  • For each value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• unconstrained by its maximum number of occurrences (i.e.,Β vβˆ‰π’±), there is an arc, labelled by πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš•, from the state s vk to the state s vk+1 for all k in [1,πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—-1]. There is also a loop, labelled by πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš•, from state s vk to the state s vk for k=πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—.

  • For each value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• constrained by its maximum number of occurrences (i.e.,Β vβˆˆπ’±), there is an arc, labelled by πš…π™°π™»πš„π™΄πš‚[w].πšŸπšŠπš•, from state s vk to state s w1 (v<w) for all k in [πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš—,πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πšŠπš‘] and for all w such that βˆ€u∈[v+1,w-1]:πš…π™°π™»πš„π™΄πš‚[u].πš˜πš–πš’πš—=0.

  • For each value πš…π™°π™»πš„π™΄πš‚[v].πšŸπšŠπš• unconstrained by its maximum number of occurrences (i.e.,Β vβˆ‰π’±), there is an arc, labelled by πš…π™°π™»πš„π™΄πš‚[w].πšŸπšŠπš•, from state s vk to state s w1 (v<w) for k=πš…π™°π™»πš„π™΄πš‚[v].πš˜πš–πš’πš— and for all w such that βˆ€u∈[v+1,w-1]:πš…π™°π™»πš„π™΄πš‚[u].πš˜πš–πš’πš—=0.

FigureΒ 5.160.2 depicts the automaton associated with the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint of the Example slot. For this purpose we assume without loss of generality that we have four decision variables that all take their potential values within interval [3,8]. Consequently, values 4, 7 and 8 are first added to the items of the πš…π™°π™»πš„π™΄πš‚ collection. Both values 3 and 6 are unconstrained by their respective maximum number of occurrences. Therefore their πš˜πš–πšŠπš‘ attributes are respectively reduced to 2 and 1. All other values, namely values 4, 5, 7 and 8, are constrained values. The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint holds since the corresponding sequence of visited states, s 00 s 11 s 12 s 41 s 61 , ends up in a terminal state (i.e.,Β terminal states are depicted by thick circles in the figure). Note that non initial states are first indexed by the position of an item within the πš…π™°π™»πš„π™΄πš‚ collection, and not by the value itself (e.g.,Β within s 12 the 1 designates value 3). For instance state s 11 depicts the fact that the automaton has already recognised one single occurrence of value 3, while s 12 corresponds to the fact that the automaton has already seen at least two occurrences of value 3.The at least comes from the loop on state s 12 .

Figure 5.160.2. Automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint of the Example slot: the path corresponding to the solution 〈3,3,6,8βŒͺ is depicted by thick arcs
ctrs/increasing_global_cardinality1