5.209. max_size_set_of_consecutive_var

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

πš–πšŠπš‘_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš›(π™Όπ™°πš‡,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™Όπ™°πš‡πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
π™Όπ™°πš‡β‰₯1
π™Όπ™°πš‡β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

π™Όπ™°πš‡ is the size of the largest set of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that all take their value in a set of consecutive values.

Example
6,πšŸπšŠπš›-3,πšŸπšŠπš›-1,πšŸπšŠπš›-3,πšŸπšŠπš›-7,πšŸπšŠπš›-4,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-8,πšŸπšŠπš›-7,πšŸπšŠπš›-6

In the example, the two sets {3,1,3,4,1,2} and {7,8,7,6} take respectively their values in the two following sets of consecutive values {1,2,3,4} and {6,7,8}. Consequently, the πš–πšŠπš‘_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš› constraint holds since the cardinality of the largest set of variables is 6.

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • All occurrences of two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped.

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

See also

common keyword: πš—πšœπšŽπš_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš•πšžπšŽπšœΒ (consecutive values).

Keywords

characteristic of a constraint: consecutive values, maximum.

constraint type: value constraint.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŠπš‹πšœ(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›-πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›)≀1
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂=π™Όπ™°πš‡

Graph model

Since the arc constraint is symmetric each strongly connected component of the final graph corresponds exactly to one connected component of the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.209.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property, we show the largest strongly connected component of the final graph.

Figure 5.209.1. Initial and final graph of the πš–πšŠπš‘_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš› constraint
ctrs/max_size_set_of_consecutive_varA
(a)
ctrs/max_size_set_of_consecutive_varB
(b)