## 5.72. colored_matrix

Origin

KOALOG

Constraint

$\mathrm{𝚌𝚘𝚕𝚘𝚛𝚎𝚍}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}\left(𝙲,𝙻,𝙺,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\mathrm{𝙲𝙿𝚁𝙾𝙹},\mathrm{𝙻𝙿𝚁𝙾𝙹}\right)$

Synonyms

$\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛𝚎𝚍}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$, $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$, $\mathrm{𝚌𝚊𝚛𝚍}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$.

Arguments
 $𝙲$ $\mathrm{𝚒𝚗𝚝}$ $𝙻$ $\mathrm{𝚒𝚗𝚝}$ $𝙺$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚕𝚒𝚗𝚎}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙲𝙿𝚁𝙾𝙹}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚗𝚘𝚌𝚌}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙻𝙿𝚁𝙾𝙹}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚕𝚒𝚗𝚎}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚗𝚘𝚌𝚌}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $𝙲\ge 0$ $𝙻\ge 0$ $𝙺\ge 0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\left[\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗},\mathrm{𝚕𝚒𝚗𝚎},\mathrm{𝚟𝚊𝚛}\right]\right)$ $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\left[\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗},\mathrm{𝚕𝚒𝚗𝚎}\right]\right)$ $|\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}|=𝙲*𝙻+𝙲+𝙻+1$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}\ge 0$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}\le 𝙲$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚕𝚒𝚗𝚎}\ge 0$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚕𝚒𝚗𝚎}\le 𝙻$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚟𝚊𝚛}\ge 0$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚟𝚊𝚛}\le 𝙺$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙲𝙿𝚁𝙾𝙹},\left[\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗},\mathrm{𝚟𝚊𝚕},\mathrm{𝚗𝚘𝚌𝚌}\right]\right)$ $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$$\left(\mathrm{𝙲𝙿𝚁𝙾𝙹},\left[\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗},\mathrm{𝚟𝚊𝚕}\right]\right)$ $|\mathrm{𝙲𝙿𝚁𝙾𝙹}|=𝙲*𝙺+𝙲+𝙺+1$ $\mathrm{𝙲𝙿𝚁𝙾𝙹}.\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}\ge 0$ $\mathrm{𝙲𝙿𝚁𝙾𝙹}.\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}\le 𝙲$ $\mathrm{𝙲𝙿𝚁𝙾𝙹}.\mathrm{𝚟𝚊𝚕}\ge 0$ $\mathrm{𝙲𝙿𝚁𝙾𝙹}.\mathrm{𝚟𝚊𝚕}\le 𝙺$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙻𝙿𝚁𝙾𝙹},\left[\mathrm{𝚕𝚒𝚗𝚎},\mathrm{𝚟𝚊𝚕},\mathrm{𝚗𝚘𝚌𝚌}\right]\right)$ $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$$\left(\mathrm{𝙻𝙿𝚁𝙾𝙹},\left[\mathrm{𝚕𝚒𝚗𝚎},\mathrm{𝚟𝚊𝚕}\right]\right)$ $|\mathrm{𝙻𝙿𝚁𝙾𝙹}|=𝙻*𝙺+𝙻+𝙺+1$ $\mathrm{𝙻𝙿𝚁𝙾𝙹}.\mathrm{𝚕𝚒𝚗𝚎}\ge 0$ $\mathrm{𝙻𝙿𝚁𝙾𝙹}.\mathrm{𝚕𝚒𝚗𝚎}\le 𝙻$ $\mathrm{𝙻𝙿𝚁𝙾𝙹}.\mathrm{𝚟𝚊𝚕}\ge 0$ $\mathrm{𝙻𝙿𝚁𝙾𝙹}.\mathrm{𝚟𝚊𝚕}\le 𝙺$
Purpose

Given a matrix of domain variables, imposes a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint involving cardinality variables on each column and each row of the matrix.

Example
$\left(\begin{array}{c}1,2,4,〈\begin{array}{ccc}\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚛}-3,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚛}-1,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚛}-3,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚛}-4,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚛}-4,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚛}-3\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚟𝚊𝚕}-0\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚟𝚊𝚕}-1\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚟𝚊𝚕}-2\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌}-2,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-0\hfill & \mathrm{𝚟𝚊𝚕}-4\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚟𝚊𝚕}-0\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚟𝚊𝚕}-1\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚟𝚊𝚕}-2\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚌𝚘𝚕𝚞𝚖𝚗}-1\hfill & \mathrm{𝚟𝚊𝚕}-4\hfill & \mathrm{𝚗𝚘𝚌𝚌}-2\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚕}-0\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚕}-1\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚕}-2\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-0\hfill & \mathrm{𝚟𝚊𝚕}-4\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚕}-0\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚕}-1\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚕}-2\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-1\hfill & \mathrm{𝚟𝚊𝚕}-4\hfill & \mathrm{𝚗𝚘𝚌𝚌}-1,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚕}-0\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚕}-1\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚕}-2\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌}-2,\hfill \\ \mathrm{𝚕𝚒𝚗𝚎}-2\hfill & \mathrm{𝚟𝚊𝚕}-4\hfill & \mathrm{𝚗𝚘𝚌𝚌}-0\hfill \end{array}〉\hfill \end{array}\right)$
Typical
 $𝙲\ge 1$ $𝙻\ge 1$ $𝙺\ge 1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.\mathrm{𝚟𝚊𝚛}\right)>1$
Arg. properties
• Functional dependency: $\mathrm{𝙲𝙿𝚁𝙾𝙹}.\mathrm{𝚗𝚘𝚌𝚌}$ determined by $𝙲$, $𝙻$ and $𝙺$.

• Functional dependency: $\mathrm{𝙻𝙿𝚁𝙾𝙹}.\mathrm{𝚗𝚘𝚌𝚌}$ determined by $𝙲$, $𝙻$ and $𝙺$.

Remark

Within [ReginGomes04] the $\mathrm{𝚌𝚘𝚕𝚘𝚛𝚎𝚍}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$ constraint is called $\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚖𝚊𝚝𝚛𝚒𝚡}$.

Algorithm

The filtering algorithm described in [ReginGomes04] is based on network flow and does not achieve arc-consistency in general. However, when the number of values is restricted to two, the algorithm [ReginGomes04] achieves arc-consistency on the variables of the matrix. This corresponds in fact to a generalisation of the problem called "Matrices composed of 0's and 1's" presented by Ford and Fulkerson [FordFulkerson62].

related to a common problem: $\mathrm{𝚜𝚊𝚖𝚎}$ (matrix reconstruction problem).