5.399. symmetric_gcc
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
Put in relation two sets: for each element of one set gives the corresponding elements of the other set to which it is associated. In addition, enforce a cardinality constraint on the number of occurrences of each value.
- Example
-
The constraint holds since:
,
,
,
,
,
,
The number of elements of is equal to 1,
The number of elements of is equal to 1,
The number of elements of is equal to 2,
The number of elements of is equal to 2,
The number of elements of is equal to 3,
The number of elements of is equal to 1,
The number of elements of is equal to 2,
The number of elements of is equal to 0.
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
- Usage
The most simple example of applying is a variant of personnel assignment problem, where one person can be assigned to perform between and jobs, and every job requires between and persons. In addition every job requires different kind of skills. The previous problem can be modelled as follows:
For each person we create an item of the collection,
For each job we create an item of the collection,
There is an arc between a person and the particular job if this person is qualified to perform it.
- Remark
The constraint generalises the constraint by allowing a variable to take more than one value. It corresponds to a variant of the constraint described inΒ [KocjanKreuger04] where the occurrence variables of the and collections are replaced by fixed intervals.
- See also
common keyword: Β (constraint involving set variables).
specialisation: Β ( replaced by ).
- Keywords
-
combinatorial object: relation.
constraint arguments: constraint involving set variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph model
The graph model used for the is similar to the one used in the or in the constraints: we use an equivalence in the arc constraint and ask all arc constraints to hold.
PartsΒ (A) andΒ (B) of FigureΒ 5.399.1 respectively show the initial and final graph. Since we use the graph property, all the arcs of the final graph are stressed in bold.
Figure 5.399.1. Initial and final graph of the constraint
(a) (b) - Signature
Since we use the arc generator on the collections and , the number of arcs of the initial graph is equal to . Therefore the maximum number of arcs of the final graph is also equal to and we can rewrite to . So we can simplify to .