5.216. min_size_set_of_consecutive_var

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

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

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

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

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

In the example, the two parts 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 smallest set of variables is 4.

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

application area: assignment.

characteristic of a constraint: consecutive values, minimum.

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.216.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 graph property, we show the smallest strongly connected component of the final graph.

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