5.138. global_cardinality

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHARME [OplobeduMarcovitchTourbier89]

Constraint

๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚,๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚)

Synonyms

๐šŒ๐š˜๐šž๐š—๐š, ๐š๐š’๐šœ๐š๐š›๐š’๐š‹๐šž๐š๐šŽ, ๐š๐š’๐šœ๐š๐š›๐š’๐š‹๐šž๐š๐š’๐š˜๐š—, ๐š๐šŒ๐šŒ, ๐šŒ๐šŠ๐š›๐š_๐šŸ๐šŠ๐š›_๐š๐šŒ๐šŒ, ๐šŽ๐š๐šŒ๐šŒ, ๐šŽ๐šก๐š๐šŽ๐š—๐š๐šŽ๐š_๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข.

Arguments
๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›)
๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š•-๐š’๐š—๐š,๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-๐š๐šŸ๐šŠ๐š›)
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚,๐šŸ๐šŠ๐š›)
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚,[๐šŸ๐šŠ๐š•,๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ])
๐š๐š’๐šœ๐š๐š’๐š—๐šŒ๐š(๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚,๐šŸ๐šŠ๐š•)
๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚.๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽโ‰ฅ0
๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚.๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽโ‰ค|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|
Purpose

Each value ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐šŸ๐šŠ๐š• (1โ‰คiโ‰ค|๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚|) should be taken by exactly ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ variables of the ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ collection.

Example
3,3,8,6,๐šŸ๐šŠ๐š•-3๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-2,๐šŸ๐šŠ๐š•-5๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-0,๐šŸ๐šŠ๐š•-6๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-1

The ๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข constraint holds since values 3, 5 and 6 respectively occur 2, 0 and 1 times within the collection โŒฉ3,3,8,6โŒช and since no constraint was specified for value 8.

Typical
|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›)>1
|๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚.๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ)>1
|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|>|๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚|
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.

Usage

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 S=(s 0 ,s 1 ,...,s n ) is magic if and only if there are s i occurrences of i in S for each integer i ranging from 0 to n. This leads to the following model:

๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข๐šŸ๐šŠ๐š›-s 0 ,๐šŸ๐šŠ๐š›-s 1 ,...,๐šŸ๐šŠ๐š›-s n ,๐šŸ๐šŠ๐š•-0๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-s 0 ,๐šŸ๐šŠ๐š•-1๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-s 1 ,โ‹ฎ๐šŸ๐šŠ๐š•-n๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ-s n
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 v a domain variable that indicates how many time value v 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.

The ๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข constraint can be seen as a system (i.e.,ย a conjunction) of ๐šŠ๐š–๐š˜๐š—๐š constraints.

When all count variables (i.e.,ย the variables ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ with iโˆˆ[1,|๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚|]) 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 ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ is replaced by the corresponding interval [๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ ฬฒ,๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽ ยฏ]. This stands for two reasons:

An implicit necessary condition inferred by double counting with the ๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข constraint is depicted by the following expression:

โˆ‘ i=1 |๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚| ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚[i].๐šŸ๐šŠ๐š›=โˆ‘ i=1 |๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚| ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐š—๐š˜๐šŒ๐šŒ๐šž๐š›๐š›๐šŽ๐š—๐šŒ๐šŽยท๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚[i].๐šŸ๐šŠ๐š•

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].

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 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: ๐š›๐š˜๐š˜๐š๐šœ, ๐šœ๐š•๐š’๐š๐š’๐š—๐š_๐šŒ๐šŠ๐š›๐š_๐šœ๐š”๐š’๐š™0ย (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 type: value constraint, counting constraint, system of constraints.

filtering: Hall interval, bound-consistency, flow, duplicated variables, DFS-bottleneck.

modelling exercises: magic series.

puzzles: magic series, autoref.

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
ctrs/global_cardinalityActrs/global_cardinalityB
(a) (b)
Automaton

Figureย 5.138.2 depicts the automaton associated with the ๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข constraint. To each item of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ corresponds a signature variable ๐š‚ i that is equal to 0. To each item of the collection ๐š…๐™ฐ๐™ป๐š„๐™ด๐š‚ corresponds a signature variable ๐š‚ i+|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚| that is equal to 1.

Figure 5.138.2. Automaton of the ๐š๐š•๐š˜๐š‹๐šŠ๐š•_๐šŒ๐šŠ๐š›๐š๐š’๐š—๐šŠ๐š•๐š’๐š๐šข constraint
ctrs/global_cardinality1