## 5.90. correspondence

Origin

Derived from $\mathrm{𝚜𝚘𝚛𝚝}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}$ by removing the sorting condition.

Constraint

$\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}\left(\mathrm{𝙵𝚁𝙾𝙼},\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽},\mathrm{𝚃𝙾}\right)$

Arguments
 $\mathrm{𝙵𝚁𝙾𝙼}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚃𝙾}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚝𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|=|\mathrm{𝙵𝚁𝙾𝙼}|$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|=|\mathrm{𝚃𝙾}|$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\ge 1$ $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\le |\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙵𝚁𝙾𝙼},\mathrm{𝚏𝚛𝚘𝚖}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚃𝙾},\mathrm{𝚝𝚟𝚊𝚛}\right)$
Purpose

The variables of collection $\mathrm{𝙵𝚁𝙾𝙼}$ correspond to the variables of collection $\mathrm{𝚃𝙾}$ according to the permutation $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ (i.e., $\mathrm{𝙵𝚁𝙾𝙼}\left[i\right].\mathrm{𝚏𝚛𝚘𝚖}=\mathrm{𝚃𝙾}\left[\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[i\right].\mathrm{𝚟𝚊𝚛}\right].\mathrm{𝚝𝚟𝚊𝚛}$).

Example
$\left(〈1,9,1,5,2,1〉,〈6,1,3,5,4,2〉,〈9,1,1,2,5,1〉\right)$

As illustrated by Figure 5.90.1, the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint holds since:

• The first item $\mathrm{𝙵𝚁𝙾𝙼}\left[1\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[1\right].\mathrm{𝚟𝚊𝚛}={6}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The second item $\mathrm{𝙵𝚁𝙾𝙼}\left[2\right].\mathrm{𝚏𝚛𝚘𝚖}=9$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[2\right].\mathrm{𝚟𝚊𝚛}={1}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The third item $\mathrm{𝙵𝚁𝙾𝙼}\left[3\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[3\right].\mathrm{𝚟𝚊𝚛}={3}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The fourth item $\mathrm{𝙵𝚁𝙾𝙼}\left[4\right].\mathrm{𝚏𝚛𝚘𝚖}=5$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[4\right].\mathrm{𝚟𝚊𝚛}={5}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The fifth item $\mathrm{𝙵𝚁𝙾𝙼}\left[5\right].\mathrm{𝚏𝚛𝚘𝚖}=2$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[5\right].\mathrm{𝚟𝚊𝚛}={4}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

• The sixth item $\mathrm{𝙵𝚁𝙾𝙼}\left[6\right].\mathrm{𝚏𝚛𝚘𝚖}=1$ of collection $\mathrm{𝙵𝚁𝙾𝙼}$ corresponds to the $\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}\left[6\right].\mathrm{𝚟𝚊𝚛}={2}^{th}$ item of collection $\mathrm{𝚃𝙾}$.

Typical
 $|\mathrm{𝙵𝚁𝙾𝙼}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}\right)>1$
Symmetry

All occurrences of two distinct values in $\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}$ or $\mathrm{𝚃𝙾}.\mathrm{𝚝𝚟𝚊𝚛}$ can be swapped; all occurrences of a value in $\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖}$ or $\mathrm{𝚃𝙾}.\mathrm{𝚝𝚟𝚊𝚛}$ can be renamed to any unused value.

Remark

Similar to the $\mathrm{𝚜𝚊𝚖𝚎}$ constraint except that we also provide the permutation that allows to go from the items of collection $\mathrm{𝙵𝚁𝙾𝙼}$ to the items of collection $\mathrm{𝚃𝙾}$.

Algorithm

An arc-consistency filtering algorithm for the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint is described in [Cymer12], [CymerPhD13]. The algorithm is based on the following ideas:

• First, one can map solutions to the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint to perfect matchings in a bipartite graph derived from the domain of the variables of the constraint in the following way: to each variable of the $\mathrm{𝙵𝚁𝙾𝙼}$ collection there is a from vertex; similarly, to each variable of the $\mathrm{𝚃𝙾}$ collection there is a to vertex; finally, there is an edge between the ${i}^{th}$ from vertex and the ${j}^{th}$ to vertex if and only if the corresponding domains intersect and if $j$ belongs to the domain of the ${i}^{th}$ permutation variable.

• Second, Dulmage-Mendelsohn decomposition [DulmageMendelsohn58] is used to characterise all edges that do not belong to any perfect matching, and therefore prune the corresponding variables.

specialisation: $\mathrm{𝚜𝚊𝚖𝚎}$ ($\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ parameter removed).

Keywords
Derived Collection
$\mathrm{𝚌𝚘𝚕}\left(\begin{array}{c}\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}-\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝚍𝚟𝚊𝚛},\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right),\hfill \\ \mathrm{𝚒𝚝𝚎𝚖}\left(\mathrm{𝚏𝚛𝚘𝚖}-\mathrm{𝙵𝚁𝙾𝙼}.\mathrm{𝚏𝚛𝚘𝚖},\mathrm{𝚟𝚊𝚛}-\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}.\mathrm{𝚟𝚊𝚛}\right)\right]\hfill \end{array}\right)$
Arc input(s)

$\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ $\mathrm{𝚃𝙾}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗},\mathrm{𝚝𝚘}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚏𝚛𝚘𝚖}=\mathrm{𝚝𝚘}.\mathrm{𝚝𝚟𝚊𝚛}$ $•\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚝𝚘}.\mathrm{𝚔𝚎𝚢}$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$

Graph class
 $•$$\mathrm{𝙰𝙲𝚈𝙲𝙻𝙸𝙲}$ $•$$\mathrm{𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴}$ $•$$\mathrm{𝙽𝙾}_\mathrm{𝙻𝙾𝙾𝙿}$

Graph model

Parts (A) and (B) of Figure 5.90.2 respectively show the initial and final graph associated with the Example slot. In both graphs the source vertices correspond to the derived collection $\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$, while the sink vertices correspond to the collection $\mathrm{𝚃𝙾}$. Since the final graph contains exactly $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ arcs the $\mathrm{𝚌𝚘𝚛𝚛𝚎𝚜𝚙𝚘𝚗𝚍𝚎𝚗𝚌𝚎}$ constraint holds. As we use the $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the arcs of the final graph are stressed in bold.

Signature

Because of the second condition $\mathrm{𝚏𝚛𝚘𝚖}_\mathrm{𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚝𝚘}.\mathrm{𝚔𝚎𝚢}$ of the arc constraint and since both, the $\mathrm{𝚟𝚊𝚛}$ attributes of the collection $\mathrm{𝙵𝚁𝙾𝙼}_\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}$ and the $\mathrm{𝚔𝚎𝚢}$ attributes of the collection $\mathrm{𝚃𝙾}$ are all-distinct, the final graph contains at most $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ arcs. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}$ $=$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$ to $\mathrm{𝐍𝐀𝐑𝐂}$ $\ge$ $|\mathrm{𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽}|$. This leads to simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.