Global Constraint Catalog: Csymmetric

5.398. symmetric_cardinality

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ by W. Kocjan.

Constraint

$𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢 (𝚅𝙰𝚁𝚂, 𝚅𝙰𝙻𝚂)$

Arguments

$𝚅𝙰𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍𝚟𝚊𝚛 - 𝚒𝚗𝚝, 𝚟𝚊𝚛 - 𝚜𝚟𝚊𝚛, 𝚕 - 𝚒𝚗𝚝, 𝚞 - 𝚒𝚗𝚝)$
$𝚅𝙰𝙻𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍𝚟𝚊𝚕 - 𝚒𝚗𝚝, 𝚟𝚊𝚕 - 𝚜𝚟𝚊𝚛, 𝚕 - 𝚒𝚗𝚝, 𝚞 - 𝚒𝚗𝚝)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝚂, [𝚒𝚍𝚟𝚊𝚛, 𝚟𝚊𝚛, 𝚕, 𝚞])

| 𝚅𝙰𝚁𝚂 | \geq 1

𝚅𝙰𝚁𝚂 . 𝚒𝚍𝚟𝚊𝚛 \geq 1

𝚅𝙰𝚁𝚂 . 𝚒𝚍𝚟𝚊𝚛 \leq | 𝚅𝙰𝚁𝚂 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝚁𝚂, 𝚒𝚍𝚟𝚊𝚛)

𝚅𝙰𝚁𝚂 . 𝚕 \geq 0

𝚅𝙰𝚁𝚂 . 𝚕 \leq 𝚅𝙰𝚁𝚂 . 𝚞

𝚅𝙰𝚁𝚂 . 𝚞 \leq | 𝚅𝙰𝙻𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚂, [𝚒𝚍𝚟𝚊𝚕, 𝚟𝚊𝚕, 𝚕, 𝚞])

| 𝚅𝙰𝙻𝚂 | \geq 1

𝚅𝙰𝙻𝚂 . 𝚒𝚍𝚟𝚊𝚕 \geq 1

𝚅𝙰𝙻𝚂 . 𝚒𝚍𝚟𝚊𝚕 \leq | 𝚅𝙰𝙻𝚂 |

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚂, 𝚒𝚍𝚟𝚊𝚕)

𝚅𝙰𝙻𝚂 . 𝚕 \geq 0

𝚅𝙰𝙻𝚂 . 𝚕 \leq 𝚅𝙰𝙻𝚂 . 𝚞

𝚅𝙰𝙻𝚂 . 𝚞 \leq | 𝚅𝙰𝚁𝚂 |

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, it constraints the number of elements associated with each element to be in a given interval.

Example

(\begin{matrix} 〈\begin{matrix} 𝚒𝚍𝚟𝚊𝚛 - 1 & 𝚟𝚊𝚛 - {3} & 𝚕 - 0 & 𝚞 - 1, \\ 𝚒𝚍𝚟𝚊𝚛 - 2 & 𝚟𝚊𝚛 - {1} & 𝚕 - 1 & 𝚞 - 2, \\ 𝚒𝚍𝚟𝚊𝚛 - 3 & 𝚟𝚊𝚛 - {1, 2} & 𝚕 - 1 & 𝚞 - 2, \\ 𝚒𝚍𝚟𝚊𝚛 - 4 & 𝚟𝚊𝚛 - {1, 3} & 𝚕 - 2 & 𝚞 - 3 \end{matrix}〉, \\ 〈\begin{matrix} 𝚒𝚍𝚟𝚊𝚕 - 1 & 𝚟𝚊𝚕 - {2, 3, 4} & 𝚕 - 3 & 𝚞 - 4, \\ 𝚒𝚍𝚟𝚊𝚕 - 2 & 𝚟𝚊𝚕 - {3} & 𝚕 - 1 & 𝚞 - 1, \\ 𝚒𝚍𝚟𝚊𝚕 - 3 & 𝚟𝚊𝚕 - {1, 4} & 𝚕 - 1 & 𝚞 - 2, \\ 𝚒𝚍𝚟𝚊𝚕 - 4 & 𝚟𝚊𝚕 - \emptyset & 𝚕 - 0 & 𝚞 - 1 \end{matrix}〉 \end{matrix})

The $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint holds since:

$3 \in 𝚅𝙰𝚁𝚂 [1] . 𝚟𝚊𝚛 \Leftrightarrow 1 \in 𝚅𝙰𝙻𝚂 [3] . 𝚟𝚊𝚕$ ,
$1 \in 𝚅𝙰𝚁𝚂 [2] . 𝚟𝚊𝚛 \Leftrightarrow 2 \in 𝚅𝙰𝙻𝚂 [1] . 𝚟𝚊𝚕$ ,
$1 \in 𝚅𝙰𝚁𝚂 [3] . 𝚟𝚊𝚛 \Leftrightarrow 3 \in 𝚅𝙰𝙻𝚂 [1] . 𝚟𝚊𝚕$ ,
$2 \in 𝚅𝙰𝚁𝚂 [3] . 𝚟𝚊𝚛 \Leftrightarrow 3 \in 𝚅𝙰𝙻𝚂 [2] . 𝚟𝚊𝚕$ ,
$1 \in 𝚅𝙰𝚁𝚂 [4] . 𝚟𝚊𝚛 \Leftrightarrow 4 \in 𝚅𝙰𝙻𝚂 [1] . 𝚟𝚊𝚕$ ,
$3 \in 𝚅𝙰𝚁𝚂 [4] . 𝚟𝚊𝚛 \Leftrightarrow 4 \in 𝚅𝙰𝙻𝚂 [3] . 𝚟𝚊𝚕$ ,
The number of elements of $𝚅𝙰𝚁𝚂 [1] . 𝚟𝚊𝚛 = {3}$ belongs to interval $[0, 1]$ ,
The number of elements of $𝚅𝙰𝚁𝚂 [2] . 𝚟𝚊𝚛 = {1}$ belongs to interval $[1, 2]$ ,
The number of elements of $𝚅𝙰𝚁𝚂 [3] . 𝚟𝚊𝚛 = {1, 2}$ belongs to interval $[1, 2]$ ,
The number of elements of $𝚅𝙰𝚁𝚂 [4] . 𝚟𝚊𝚛 = {1, 3}$ belongs to interval $[2, 3]$ ,
The number of elements of $𝚅𝙰𝙻𝚂 [1] . 𝚟𝚊𝚕 = {2, 3, 4}$ belongs to interval $[3, 4]$ ,
The number of elements of $𝚅𝙰𝙻𝚂 [2] . 𝚟𝚊𝚕 = {3}$ belongs to interval $[1, 1]$ ,
The number of elements of $𝚅𝙰𝙻𝚂 [3] . 𝚟𝚊𝚕 = {1, 4}$ belongs to interval $[1, 2]$ ,
The number of elements of $𝚅𝙰𝙻𝚂 [4] . 𝚟𝚊𝚕 = \emptyset$ belongs to interval $[0, 1]$ .

Typical

| 𝚅𝙰𝚁𝚂 | > 1

| 𝚅𝙰𝙻𝚂 | > 1

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 $n$ and $m$ $(n \leq m)$ jobs, and every job requires between $p$ and $q$ $(p \leq q)$ 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.

Algorithm

A first flow-based arc-consistency algorithm for the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint is described in [KocjanKreuger04]. A second arc-consistency filtering algorithm exploiting matching theory [DulmageMendelsohn58] is described in [Cymer12], [CymerPhD13].

generalisation: $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚐𝚌𝚌$ ( $𝚏𝚒𝚡𝚎𝚍$ $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

root concept: $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ .

used in graph description: $𝚒𝚗_𝚜𝚎𝚝$ .

Keywords

application area: assignment.

combinatorial object: relation.

constraint arguments: constraint involving set variables.

constraint type: decomposition, timetabling constraint.

filtering: flow, bipartite matching.

Arc input(s)

$𝚅𝙰𝚁𝚂$ $𝚅𝙰𝙻𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚜, 𝚟𝚊𝚕𝚜)

Arc arity

Arc constraint(s)

•

𝚒𝚗_𝚜𝚎𝚝

(𝚟𝚊𝚛𝚜 . 𝚒𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚜 . 𝚟𝚊𝚕) \Leftrightarrow

𝚒𝚗_𝚜𝚎𝚝

(𝚟𝚊𝚕𝚜 . 𝚒𝚍𝚟𝚊𝚕, 𝚟𝚊𝚛𝚜 . 𝚟𝚊𝚛)

• 𝚟𝚊𝚛𝚜 . 𝚕 \leq 𝚌𝚊𝚛𝚍_𝚜𝚎𝚝 (𝚟𝚊𝚛𝚜 . 𝚟𝚊𝚛)

• 𝚟𝚊𝚛𝚜 . 𝚞 \geq 𝚌𝚊𝚛𝚍_𝚜𝚎𝚝 (𝚟𝚊𝚛𝚜 . 𝚟𝚊𝚛)

• 𝚟𝚊𝚕𝚜 . 𝚕 \leq 𝚌𝚊𝚛𝚍_𝚜𝚎𝚝 (𝚟𝚊𝚕𝚜 . 𝚟𝚊𝚕)

• 𝚟𝚊𝚕𝚜 . 𝚞 \geq 𝚌𝚊𝚛𝚍_𝚜𝚎𝚝 (𝚟𝚊𝚕𝚜 . 𝚟𝚊𝚕)

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.398.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, all the arcs of the final graph are stressed in bold.

Figure 5.398.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 $| 𝚅𝙰𝚁𝚂 | \cdot | 𝚅𝙰𝙻𝚂 |$ . Therefore the maximum number of arcs of the final graph is also equal to $| 𝚅𝙰𝚁𝚂 | \cdot | 𝚅𝙰𝙻𝚂 |$ and we can rewrite $𝐍𝐀𝐑𝐂 = | 𝚅𝙰𝚁𝚂 | \cdot | 𝚅𝙰𝙻𝚂 |$ to $𝐍𝐀𝐑𝐂 \geq | 𝚅𝙰𝚁𝚂 | \cdot | 𝚅𝙰𝙻𝚂 |$ . So we can simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Global Constraint Catalog

5. Global Constraint Catalogue

5.398. symmetric_cardinality

Figure 5.398.1. Initial and final graph of the 𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢 constraint

Figure 5.398.1. Initial and final graph of the $𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ constraint