Global Constraint Catalog: Csize_max_starting_seq

5.291. size_max_starting_seq_alldifferent

DESCRIPTION

LINKS

GRAPH

Origin

Inspired by $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Constraint

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

Synonyms

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

Arguments

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

Restrictions

𝚂𝙸𝚉𝙴 \geq 0

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

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

Example

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

The $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds since the constraint $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 9, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5 〉)$ holds and since $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - 9, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2 〉)$ does not hold.

Symmetry

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

Remark

A conditional constraint [MittalFalkenhainer90] with the specific structure that one can relax the constraints on the last variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Keywords

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

combinatorial object: sequence.

constraint type: sliding sequence constraint, open constraint, conditional constraint.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻_1

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗

Arc arity

*

Arc constraint(s)

𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝

(𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗)

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝚂𝙸𝚉𝙴

Graph model

Note that this is an example where the arc constraints do not have the same arity. However they correspond to the same constraint.

Parts (A) and (B) of Figure 5.291.1 respectively show the initial and final graph associated with the Example slot.

Figure 5.291.1. Initial and final graph of the $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

ctrs/size_max_starting_seq_alldifferent1

Global Constraint Catalog

5. Global Constraint Catalogue

5.291. size_max_starting_seq_alldifferent

Figure 5.291.1. Initial and final graph of the $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

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

Global Constraint Catalog

5. Global Constraint Catalogue

5.291. size_max_starting_seq_alldifferent

Figure 5.291.1. Initial and final graph of the 𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint

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

Figure 5.291.1. Initial and final graph of the $𝚜𝚒𝚣𝚎_𝚖𝚊𝚡_𝚜𝚝𝚊𝚛𝚝𝚒𝚗𝚐_𝚜𝚎𝚚_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint