Global Constraint Catalog: Ccolored

5.72. colored_matrix

DESCRIPTION

LINKS

Origin

KOALOG

Constraint

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

Synonyms

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

Arguments

$𝙲$	$𝚒𝚗𝚝$
$𝙻$	$𝚒𝚗𝚝$
$𝙺$	$𝚒𝚗𝚝$
$𝙼𝙰𝚃𝚁𝙸𝚇$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚌𝚘𝚕𝚞𝚖𝚗 - 𝚒𝚗𝚝, 𝚕𝚒𝚗𝚎 - 𝚒𝚗𝚝, 𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙲𝙿𝚁𝙾𝙹$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚌𝚘𝚕𝚞𝚖𝚗 - 𝚒𝚗𝚝, 𝚟𝚊𝚕 - 𝚒𝚗𝚝, 𝚗𝚘𝚌𝚌 - 𝚍𝚟𝚊𝚛)$
$𝙻𝙿𝚁𝙾𝙹$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚕𝚒𝚗𝚎 - 𝚒𝚗𝚝, 𝚟𝚊𝚕 - 𝚒𝚗𝚝, 𝚗𝚘𝚌𝚌 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙲 \geq 0

𝙻 \geq 0

𝙺 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙼𝙰𝚃𝚁𝙸𝚇, [𝚌𝚘𝚕𝚞𝚖𝚗, 𝚕𝚒𝚗𝚎, 𝚟𝚊𝚛])

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙼𝙰𝚃𝚁𝙸𝚇, [𝚌𝚘𝚕𝚞𝚖𝚗, 𝚕𝚒𝚗𝚎])

| 𝙼𝙰𝚃𝚁𝙸𝚇 | = 𝙲 * 𝙻 + 𝙲 + 𝙻 + 1

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚌𝚘𝚕𝚞𝚖𝚗 \geq 0

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚌𝚘𝚕𝚞𝚖𝚗 \leq 𝙲

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚕𝚒𝚗𝚎 \geq 0

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚕𝚒𝚗𝚎 \leq 𝙻

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟𝚊𝚛 \geq 0

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟𝚊𝚛 \leq 𝙺

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙲𝙿𝚁𝙾𝙹, [𝚌𝚘𝚕𝚞𝚖𝚗, 𝚟𝚊𝚕, 𝚗𝚘𝚌𝚌])

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙲𝙿𝚁𝙾𝙹, [𝚌𝚘𝚕𝚞𝚖𝚗, 𝚟𝚊𝚕])

| 𝙲𝙿𝚁𝙾𝙹 | = 𝙲 * 𝙺 + 𝙲 + 𝙺 + 1

𝙲𝙿𝚁𝙾𝙹 . 𝚌𝚘𝚕𝚞𝚖𝚗 \geq 0

𝙲𝙿𝚁𝙾𝙹 . 𝚌𝚘𝚕𝚞𝚖𝚗 \leq 𝙲

𝙲𝙿𝚁𝙾𝙹 . 𝚟𝚊𝚕 \geq 0

𝙲𝙿𝚁𝙾𝙹 . 𝚟𝚊𝚕 \leq 𝙺

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙻𝙿𝚁𝙾𝙹, [𝚕𝚒𝚗𝚎, 𝚟𝚊𝚕, 𝚗𝚘𝚌𝚌])

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙻𝙿𝚁𝙾𝙹, [𝚕𝚒𝚗𝚎, 𝚟𝚊𝚕])

| 𝙻𝙿𝚁𝙾𝙹 | = 𝙻 * 𝙺 + 𝙻 + 𝙺 + 1

𝙻𝙿𝚁𝙾𝙹 . 𝚕𝚒𝚗𝚎 \geq 0

𝙻𝙿𝚁𝙾𝙹 . 𝚕𝚒𝚗𝚎 \leq 𝙻

𝙻𝙿𝚁𝙾𝙹 . 𝚟𝚊𝚕 \geq 0

𝙻𝙿𝚁𝙾𝙹 . 𝚟𝚊𝚕 \leq 𝙺

Purpose

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

Example

(\begin{matrix} 1, 2, 4, 〈\begin{matrix} 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚛 - 3, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚛 - 1, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚛 - 3, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚛 - 4, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚛 - 4, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚛 - 3 \end{matrix}〉, \\ 〈\begin{matrix} 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚟𝚊𝚕 - 0 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚟𝚊𝚕 - 3 & 𝚗𝚘𝚌𝚌 - 2, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 0 & 𝚟𝚊𝚕 - 4 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚟𝚊𝚕 - 0 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚟𝚊𝚕 - 3 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚌𝚘𝚕𝚞𝚖𝚗 - 1 & 𝚟𝚊𝚕 - 4 & 𝚗𝚘𝚌𝚌 - 2 \end{matrix}〉, \\ 〈\begin{matrix} 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚕 - 0 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚕 - 3 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚕𝚒𝚗𝚎 - 0 & 𝚟𝚊𝚕 - 4 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚕 - 0 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚕 - 3 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 1 & 𝚟𝚊𝚕 - 4 & 𝚗𝚘𝚌𝚌 - 1, \\ 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚕 - 0 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚕 - 1 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚕 - 2 & 𝚗𝚘𝚌𝚌 - 0, \\ 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚕 - 3 & 𝚗𝚘𝚌𝚌 - 2, \\ 𝚕𝚒𝚗𝚎 - 2 & 𝚟𝚊𝚕 - 4 & 𝚗𝚘𝚌𝚌 - 0 \end{matrix}〉 \end{matrix})

Typical

𝙲 \geq 1

𝙻 \geq 1

𝙺 \geq 1

𝚛𝚊𝚗𝚐𝚎

(𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟𝚊𝚛) > 1

Arg. properties

Functional dependency: $𝙲𝙿𝚁𝙾𝙹 . 𝚗𝚘𝚌𝚌$ determined by $𝙲$ , $𝙻$ and $𝙺$ .
Functional dependency: $𝙻𝙿𝚁𝙾𝙹 . 𝚗𝚘𝚌𝚌$ determined by $𝙲$ , $𝙻$ and $𝙺$ .

Remark

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

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

part of system of constraints: $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ .

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

Keywords

constraint arguments: pure functional dependency.

constraint type: system of constraints, predefined constraint, timetabling constraint.

modelling: functional dependency, matrix, matrix model.

Global Constraint Catalog

5. Global Constraint Catalogue

5.72. colored_matrix