Global Constraint Catalog: Cmax_occ_of_consecutive_tuples_of

5.245. max_occ_of_consecutive_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} 〉$ of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ (with $v_{1}, v_{2}, \dots, v_{m}$ distinct) we generate all vectors $〈 u_{1}, u_{2}, \dots, u_{𝙺} 〉$ such that $u_{1} = v_{p}$ , $u_{2} = v_{p + 1}$ , $\dots$ , $u_{𝙺} = v_{p + 𝙺 - 1}$ or $u_{1} = v_{p + 𝙺 - 1}$ , $u_{2} = v_{p + 𝙺 - 2}$ , $\dots$ , $u_{𝙺} = v_{p}$ (with $1 \leq p \leq m - 𝙺 + 1$ ).

Example

(1, 2, 〈𝚟𝚎𝚌 - 〈4, 1, 3〉, 𝚟𝚎𝚌 - 〈2, 7, 6〉, 𝚟𝚎𝚌 - 〈5, 9, 8〉〉)

Given the three vectors of the example we respectively generate:

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

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

Typical

𝙼𝙰𝚇 = 1

𝙺 = 2

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 2

Arg. properties

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

Usage

This constraint occurs in balanced block design problems [RosaHuang71].

Keywords

characteristic of a constraint: vector.

modelling: functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.245. max_occ_of_consecutive_tuples_of_values