Global Constraint Catalog: Csize_max_seq

5.290. size_max_seq_alldifferent

DESCRIPTION

LINKS

GRAPH

Origin

N. Beldiceanu

Constraint

$𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 (𝚂𝙸𝚉𝙴, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonyms

$𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚏𝚏$ , $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝$ , $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡𝚒𝚖𝚊𝚕_𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Arguments

$𝚂𝙸𝚉𝙴$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚂𝙸𝚉𝙴 \geq 0

𝚂𝙸𝚉𝙴 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

$𝚂𝙸𝚉𝙴$ is the size of the maximal sequence (among all possible sequences of consecutive variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ ) for which the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds.

Example

(\begin{matrix} 4, 〈\begin{matrix} 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 4, \\ 𝚟𝚊𝚛 - 5, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 7, \\ 𝚟𝚊𝚛 - 4 \end{matrix}〉 \end{matrix})

The $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds since the constraint $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7 〉)$ holds and since the following three constraints do not hold:

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2 〉)$ ,
$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7 〉)$ ,
$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 7, 𝚟𝚊𝚛 - 4 〉)$ .

Symmetry

One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Keywords

characteristic of a constraint: all different, disequality, hypergraph.

combinatorial object: sequence.

constraint type: sliding sequence constraint, conditional constraint.

Arc input(s): $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$
Arc generator: $𝑃𝐴𝑇𝐻_𝑁$ $\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗$
Arc arity: $*$
Arc constraint(s): $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗)$
Graph property(ies): $𝐍𝐀𝐑𝐂$ $= 𝚂𝙸𝚉𝙴$
Graph model: Note that this is an example of global constraint where the arc constraints do not have the same arity. However they correspond to the same type of constraint.

Global Constraint Catalog

5. Global Constraint Catalogue

5.290. size_max_seq_alldifferent

W3C: XHTML - last update: 2010-12-6. SD.