- Origin
CHARME [OplobeduMarcovitchTourbier89]
- Constraint
-
- Synonyms
,
,
,
,
,
,
.
- Arguments
| |
| |
- Restrictions
-
- Purpose
Each value (with )
should be taken by exactly
variables of the collection.
- Example
-
The constraint holds since values
3, 5 and 6 respectively occur 2, 0 and 1 times within
the collection and since no restriction was
specified for value 8.
- All solutions
Figureย 5.163.1 gives all solutions to the following non ground instance of the constraint:
, , , , , ,
, , , ,
.
- Typical
|
|
|
|
|
- Symmetries
Items of are permutable.
Items of are permutable.
An occurrence of a value of that does not belong to can be replaced by any other value that also does not belong to .
All occurrences of two distinct values in or can be swapped; all occurrences of a value in or can be renamed to any unused value.
- Arg. properties
Functional dependency: determined by and .
Contractible wrt. .
- Usage
We show how to use the constraint
in order to model the magic series problemย [VanHentenryck89]
with a 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:
- Remark
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 actually 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 possiblyOf course one could also, while generating a flow model, detect all unconstrained values in order to
generate a 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.
The constraint can be seen as a system (i.e., a conjunction)
of constraints.
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:
When all values that can be assigned to the variables of the collection
occur in the attribute of the collection,
two implicit necessary conditionsNote that such necessary conditions can be derived by
assigning an integer weight to each valueย [Simonis13],
e.g.ย 1 for the first condition, the value itself for the second condition.
inferred by double counting
with the constraint are depicted by the following expressions:
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].
In MiniZinc
(http://www.minizinc.org/)
there is also a constraint where the attribute is not necessarily initially fixed
and where a same value may occur more than once.
Their is also a constraint where all variables must be assigned
a value from the attribute.
- Algorithm
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].
- Systems
globalCardinality in Choco,
count in Gecode,
gcc in JaCoP,
global_cardinality in MiniZinc,
global_cardinality in SICStus.
- See also
common keyword:
,
,
ย (value constraint,counting constraint),
ย (counting constraint),
ย (assignment,counting constraint).
cost variant:
ย ( associated with each , pair).
implied by:
ย (forget about cost),
ย (conjoin and ).
part of system of constraints:
.
related:
,
ย (counting constraint of a set of values on maximal sequences).
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 ).
uses in its reformulation:
,
.
- Keywords
application area:
assignment.
characteristic of a constraint:
core,
automaton,
automaton with array of counters.
complexity:
3-SAT.
constraint arguments:
pure functional dependency.
constraint type:
value constraint,
counting constraint,
system of constraints.
filtering:
Hall interval,
bound-consistency,
flow,
duplicated variables,
DFS-bottleneck.
modelling:
functional dependency.
modelling exercises:
magic series.
puzzles:
magic series,
autoref.
- Cond. implications
-
ย ย ย withย
ย ย implies
ย ย ย whenย .
ย ย ย withย
ย ย implies
ย ย ย whenย .
ย ย ย withย
ย ย implies
ย ย ย whenย .
ย ย ย withย
ย ย implies
ย ย ย whenย .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies
ย ย ย whenย .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
ย ย ย withย
ย ย ย andย ย
ย ย ย andย ย
ย ย implies .
For all items of :