5.23. among
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Synonyms
, .
- Arguments
- Restrictions
- Purpose
is the number of variables of the collection that take their value in .
- Example
-
The constraint holds since exactly 3 values of the collection of variables belong to the set of values .
- All solutions
FigureΒ 5.23.1 gives all solutions to the following non ground instance of the constraint: , , , , .
Figure 5.23.1. All solutions corresponding to the non ground example of the constraint of the All solutions slot
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
An occurrence of a value of that belongs to (resp. does not belong to ) can be replaced by any other value in (resp. not in ).
- Arg. properties
Functional dependency: determined by and .
Contractible wrt. when .
Contractible wrt. when .
Aggregate: , , .
- Remark
A similar constraint called was introduced in CHIP in 1990.
The constraint can be seen as a generalisation of the constraint where we allow the attributes of the collection to be domain variables.
A generalisation of this constraint when the values of are not initially fixed is called .
When the variable (i.e.,Β the first argument of the constraint) does not occur in any other constraints of the problem, it may be operationally more efficient to replace the constraint by an constraint where is replaced by the corresponding interval . This stands for two reasons:
First, by using an constraint rather than an constraint, we avoid the filtering algorithm related to .
Second, unlike the constraint where we need to fix all its variables to get entailment, the constraint can be entailed before all its variables get fixed. As a result, this potentially avoid unnecessary calls to its filtering algorithm.
It was shown inΒ [ChabertDemassey12] that achieving bound-consistency for a conjunction of constraints where all sets of values are arbitrary intervals can be done in polynomial time.
- Algorithm
A filtering algorithm achieving arc-consistency was given by Bessière et al. in [BessiereHebrardHnichKiziltanWalsh05ERCIM], [BessiereHebrardHnichKiziltanWalsh06ERCIM].
- Systems
among in Choco, count in Gecode, among in JaCoP, among in MiniZinc.
- See also
common keyword: , , Β (value constraint), Β (counting constraint), Β (value constraint,counting constraint), , , , Β (counting constraint).
generalisation: Β ( replaced by ).
implies: , .
related: Β (can be used for expressing ), Β (counting constraint on maximal sequences).
shift of concept: Β ( replaced by and constraint applied in a sliding way), .
soft variant: Β (open constraint).
specialisation: Β ( replaced by different from 0), Β ( replaced by ), Β ( replaced by ), Β (list of replaced by list of such that = ), Β ( replaced by and replaced by one single ).
system of constraints: Β (count the number of occurrences of different values).
- Keywords
characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton.
constraint arguments: reverse of a constraint, pure functional dependency.
constraint network structure: alpha-acyclic constraint network(2), Berge-acyclic constraint network.
constraint type: value constraint, counting constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
The arc constraint corresponds to the unary constraint defined in this catalogue. Since this is a unary constraint we employ the arc generator in order to produce an initial graph with a single loop on each vertex.
PartsΒ (A) andΒ (B) of FigureΒ 5.23.2 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the loops of the final graph are stressed in bold.
Figure 5.23.2. Initial and final graph of the constraint
(a) (b)
- Automaton
FigureΒ 5.23.3 depicts a first automaton that only accepts all the solutions to the constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form already encountered. To each variable of the collection corresponds a 0-1 signature variable . The following signature constraint links and : . The automaton counts the number of variables of the collection that take their value in and finally assigns this number to .
Figure 5.23.3. Automaton (with one counter) of the constraint and its glue matrix
Figure 5.23.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the constraint: since all states variables are fixed to the unique state of the automaton, the transitions constraints share only the counter variable and the constraint network is Berge-acyclic
We now describe a second counter free automaton that also only accepts all the solutions to constraint. Without loss of generality, assume that the collection of variables contains at least one variable (i.e.,Β ). Let and respectively denote the number of variables of the collection , and the union of the domains of the variables of . Clearly, the maximum number of variables of that are assigned a value in cannot exceed the quantity . The states of the automaton that only accepts all the solutions to the constraint can be defined in the following way:
We have an initial state labelled by .
We have intermediate states labelled by . The intermediate states are indexed by the number of already encountered satisfied constraints of the form from the initial state to the state .
We have an accepting state labelled by .
Three classes of transitions are respectively defined in the following way:
There is a transition, labeled by , , from every state , , to itself.
There is a transition, labeled by , , from every state , , to the state .
There is a transition, labelled by , from every state , , to the accepting state .
This leads to an automaton that has transitions. Since the maximum value of is equal to , in the worst case we have transitions.
FigureΒ 5.23.5 depicts a counter free non deterministic automaton associated with the constraint under the hypothesis that (1)Β all variables of are assigned a value in , (2)Β is equal to 3, (3)Β corresponds to odd values. The sequence is passed to this automaton. A state represents the fact that odd values were already encountered, while represents the accepting state. A transition from to is labelled by and represents the fact that we can only go in the accepting state from a state that is compatible with the total number of odd values enforced by . Note that non determinism only occurs if there is a non-empty intersection between the set of potential values that can be assigned to the variables of and the potential value of the . While the counter free non deterministic automaton depicted by FigureΒ 5.23.5 has 5 states and 18 transitions, its minimum-state deterministic counterpart shown in FigureΒ 5.23.6 has 7 states and 23 transitions.
Figure 5.23.5. Counter free non deterministic automaton of the constraint assuming , with initial state and accepting state
Figure 5.23.6. Counter free minimum-state deterministic automaton of the constraint assuming , with initial state and accepting states , ,
We make the following final observation. Since the Symmetries slot of the constraint indicates that the variables of are permutable, and since all incoming transitions to any state of the automaton depicted by FigureΒ 5.23.5 are labelled with distinct values, we can mechanically construct from this automaton a counter free deterministic automaton that takes as input the sequence , , , rather than the sequence , , , . This is achieved by respectively making and the initial and the accepting state, and by reversing each transition.