5.259. 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)
(4,3,1,3,2)

In the first 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 corresponding πš–πš’πš—_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš› constraint holds since the cardinality of the smallest set of variables is 4.

Typical
𝙼𝙸𝙽>1
𝙼𝙸𝙽<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
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 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Arg. properties

Functional dependency: 𝙼𝙸𝙽 determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Counting
Length (n)2345678
Solutions9646257776117649209715243046721

Number of solutions for πš–πš’πš—_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš›: domains 0..n

ctrs/min_size_set_of_consecutive_var-1-tikz

ctrs/min_size_set_of_consecutive_var-2-tikz

Length (n)2345678
Total9646257776117649209715243046721
Parameter
value

1230276358057000106583422894984
27-13224803099052252211080412
3-34--135003324304590208
4--217---2293480
5---1716---
6----16159--
7-----176366-
8------2187637

Solution count for πš–πš’πš—_πšœπš’πš£πšŽ_𝚜𝚎𝚝_𝚘𝚏_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš›: domains 0..n

ctrs/min_size_set_of_consecutive_var-3-tikz

ctrs/min_size_set_of_consecutive_var-4-tikz

See also

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

Keywords

application area: assignment.

characteristic of a constraint: consecutive values, minimum.

constraint arguments: pure functional dependency.

constraint type: value constraint.

modelling: functional dependency.

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

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