Global Constraint Catalog: Cmax_occ_of_tuples_of

5.247. max_occ_of_tuples_of_values

DESCRIPTION

LINKS

Origin

Design.

Constraint

$𝚖𝚊𝚡_𝚘𝚌𝚌_𝚘𝚏_𝚝𝚞𝚙𝚕𝚎𝚜_𝚘𝚏_𝚟𝚊𝚕𝚞𝚎𝚜 (𝙼𝙰𝚇, 𝙺, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$

Type

𝚅𝙴𝙲𝚃𝙾𝚁

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Arguments

$𝙼𝙰𝚇$	$𝚒𝚗𝚝$
$𝙺$	$𝚒𝚗𝚝$
$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁, 𝚟𝚊𝚛)

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 2

𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐

(𝚅𝙴𝙲𝚃𝙾𝚁)

𝙼𝙰𝚇 \geq 1

𝙺 \geq 2

𝙺 < | 𝚅𝙴𝙲𝚃𝙾𝚁 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | \geq 1

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

Purpose

$𝙼𝙰𝚇$ is equal to the maximum number of occurrences of identical vectors derived from the vectors $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ in the following way. To each vector $〈 v_{1}, v_{2}, \dots, v_{m} 〉$ (with $v_{1} < v_{2} \land \dots \land v_{m - 1} < v_{m}$ ) of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ we generate all vectors $〈 u_{1}, u_{2}, \dots, u_{𝙺} 〉$ such that $u_{1} = v_{i_{1}}$ , $u_{2} = v_{i_{2}}$ , $\dots$ , $u_{𝙺} = v_{i_{𝙺}}$ (with $1 \leq i_{1} < i_{2} < \dots < i_{𝙺} \leq m$ ).

Example

(\begin{matrix} 1, 2, 〈\begin{matrix} 𝚟𝚎𝚌 - 〈1, 2, 4〉, \\ 𝚟𝚎𝚌 - 〈2, 3, 5〉, \\ 𝚟𝚎𝚌 - 〈3, 4, 6〉, \\ 𝚟𝚎𝚌 - 〈4, 5, 7〉, \\ 𝚟𝚎𝚌 - 〈1, 5, 6〉, \\ 𝚟𝚎𝚌 - 〈2, 6, 7〉, \\ 𝚟𝚎𝚌 - 〈1, 3, 7〉 \end{matrix}〉 \end{matrix})

Given the seven vectors of the example we respectively generate:

the pairs $〈 1, 2 〉$ , $〈 1, 4 〉$ and $〈 2, 4 〉$ from the triple $〈 1, 2, 4 〉$ ,
the pairs $〈 2, 3 〉$ , $〈 2, 5 〉$ and $〈 3, 5 〉$ from the triple $〈 2, 3, 5 〉$ ,
the pairs $〈 3, 4 〉$ , $〈 3, 6 〉$ and $〈 4, 6 〉$ from the triple $〈 3, 4, 6 〉$ ,
the pairs $〈 4, 5 〉$ , $〈 4, 7 〉$ and $〈 5, 7 〉$ from the triple $〈 4, 5, 7 〉$ ,
the pairs $〈 1, 5 〉$ , $〈 1, 6 〉$ and $〈 5, 6 〉$ from the triple $〈 1, 5, 6 〉$ ,
the pairs $〈 2, 6 〉$ , $〈 2, 7 〉$ and $〈 6, 7 〉$ from the triple $〈 2, 6, 7 〉$ ,
the pairs $〈 1, 3 〉$ , $〈 1, 7 〉$ and $〈 3, 7 〉$ from the triple $〈 1, 3, 7 〉$ .

Putting these pairs together, we get the set of pairs ${〈 1, 2 〉$ , $〈 1, 3 〉$ , $〈 1, 4 〉$ , $〈 1, 5 〉$ , $〈 1, 6 〉$ , $〈 1, 7 〉$ , $〈 2, 3 〉$ , $〈 2, 4 〉$ , $〈 2, 5 〉$ , $〈 2, 6 〉$ , $〈 2, 7 〉$ , $〈 3, 4 〉$ , $〈 3, 5 〉$ , $〈 3, 6 〉$ , $〈 3, 7 〉$ , $〈 4, 5 〉$ , $〈 4, 6 〉$ , $〈 4, 7 〉$ , $〈 5, 6 〉$ , $〈 5, 7 〉$ , $〈 6, 7 〉}$ . The $𝚖𝚊𝚡_𝚘𝚌𝚌_𝚘𝚏_𝚝𝚞𝚙𝚕𝚎𝚜_𝚘𝚏_𝚟𝚊𝚕𝚞𝚎𝚜$ constraint holds since the components of the original seven vectors are strictly increasing, and since $𝙼𝙰𝚇$ is set to one and all the generated pairs are distinct.

Typical

𝙼𝙰𝚇 \leq 2

| 𝚅𝙴𝙲𝚃𝙾𝚁 | < 𝙺 + 5

𝙺 = 2 \lor 𝙺 + 1 = | 𝚅𝙴𝙲𝚃𝙾𝚁 |

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 2

Arg. properties

Functional dependency: $𝙼𝙰𝚇$ determined by $𝙺$ and $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ .
Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ when $𝙼𝙰𝚇 = 1$ .

Usage

This constraint occurs in balanced block design problems [HellRosa72], [LindnerRosa80] such as Steiner or Kirkman triples.

implies: $𝚖𝚊𝚡_𝚘𝚌𝚌_𝚘𝚏_𝚜𝚘𝚛𝚝𝚎𝚍_𝚝𝚞𝚙𝚕𝚎𝚜_𝚘𝚏_𝚟𝚊𝚕𝚞𝚎𝚜$ .

Keywords

characteristic of a constraint: vector.

modelling: functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.247. max_occ_of_tuples_of_values