5.291. size_max_starting_seq_alldifferent

DESCRIPTIONLINKSGRAPH
Origin

Inspired by πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πšœπš’πš£πšŽ_πš–πšŠπš‘_πšœπšπšŠπš›πšπš’πš—πš_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš‚π™Έπš‰π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πšœπš’πš£πšŽ_πš–πšŠπš‘πš’πš–πšŠπš•_πšœπšπšŠπš›πšπš’πš—πš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšŠπš•πš•πšπš’πšπš, πšœπš’πš£πšŽ_πš–πšŠπš‘πš’πš–πšŠπš•_πšœπšπšŠπš›πšπš’πš—πš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš, πšœπš’πš£πšŽ_πš–πšŠπš‘πš’πš–πšŠπš•_πšœπšπšŠπš›πšπš’πš—πš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Arguments
πš‚π™Έπš‰π™΄πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš‚π™Έπš‰π™΄β‰₯0
πš‚π™Έπš‰π™΄β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
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
4,πšŸπšŠπš›-9,πšŸπšŠπš›-2,πšŸπšŠπš›-4,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-7,πšŸπšŠπš›-4

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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (all different,disequality).

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β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—

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