, , , , , , .
Each value should be taken by exactly variables of the collection.
The constraint holds since values 3, 5 and 6 respectively occur 2, 0 and 1 times within the collection and since no constraint was specified for value 8.
We show how to use the constraint in order to model the magic series problem [VanHentenryck89] with one single constraint. A non-empty finite series is magic if and only if there are occurrences of in for each integer ranging from 0 to . This leads to the following model:
This is a generalised form of the original constraint: in the original constraint [Regin96], one specifies for each value its minimum and maximum number of occurrences (i.e., see ). Here we give for each value a domain variable that indicates how many time value is effectively used. By setting the minimum and maximum values of this variable to the appropriate constants we can express the same thing as in the original constraint. However, as shown in the magic series problem, we can also use this variable in other constraints. By reduction from 3-SAT, Claude -Guy Quimper shows in [Quimper03] that it is NP -hard to achieve arc-consistency for the count variables.
A last difference with the original constraint comes from the fact that there is no constraint on the values that are not explicitly mentioned in the collection. In the original these values could not be assigned to the variables of the collection. However allowing values that are not mentioned in to be assigned to variables of can potentially avoid mentioning a huge number of unconstrained values in the collection, and as a side effect, prevent eventuallyOf course one could also, while generating a flow model, detect all unconstrained values in order to generate one single vertex in the flow model for the set of unconstrained values. generating a dense graph (i.e., see DFS-bottleneck) for the corresponding underlying flow model).
Within [BourdaisGalinierPesant03] the constraint is called . Within [ReginGomes04] the constraint is called . Within [BessiereHebrardHnichWalsh04a] the constraint is called or . This later case corresponds to the fact that some variables are duplicated within the collection.
When all count variables (i.e., the variables with ) do not occur in any other constraints of the problem, it may be operationally more efficient to replace the constraint by a constraint where each count variable is replaced by the corresponding interval . This stands for two reasons:
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.
An implicit necessary condition inferred by double counting with the constraint is depicted by the following expression:
Within [Pitrat08] the previous condition where terms involving identical variables are grouped together (i.e., rule 5 of MALICE [Pitrat01]) is mentioned as a crucial deduction rule for the autoref problem.
W.-J. van Hoeve et al. present two soft versions of the constraint in [HoevePesantRousseau04].
A flow algorithm that handles the original constraint is described in [Regin96]. The two approaches that were used to design bound-consistency algorithms for were generalised for the constraint. The algorithm in [QuimperBeekOrtizGolynskiSadjad03] identifies Hall intervals and the one in [KatrielThiel03] exploits convexity to achieve a fast implementation of the flow -based arc-consistency algorithm. The later algorithm can also compute bound-consistency for the count variables [KatrielThielConstraints05], [Katriel05]. An improved algorithm for achieving arc-consistency is described in [QuimperLopezOrtizBeekGolynski04].
- See also
cost variant: ( associated with each , pair).
implied by: (forget about cost), (conjoin and ).
shift of concept: (assignment of a to its position is ignored), (restrictions are done on nested sets of values, all starting from first value), , .
soft variant: (a defines the set of variables that are actually considered).
specialisation: (each value should occur at most once), , (individual for each value replaced by single ), (individual for each value replaced by single and replaced by ), ( replaced by ).
system of constraints: (one constraint for each and each of a of ).
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.138.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.138.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.138.1. Initial and final graph of the constraint
Figure 5.138.2 depicts the automaton associated with the constraint. To each item of the collection corresponds a signature variable that is equal to 0. To each item of the collection corresponds a signature variable that is equal to 1.
Figure 5.138.2. Automaton of the constraint