5.31. atleast_nvector

DESCRIPTIONLINKSGRAPH
Origin

Derived from πš—πšŸπšŽπšŒπšπš˜πš›

Constraint

πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›(π™½πš…π™΄π™²,πš…π™΄π™²πšƒπ™Ύπšπš‚)

Type
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
π™½πš…π™΄π™²πšπšŸπšŠπš›
πš…π™΄π™²πšƒπ™Ύπšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚟𝚎𝚌-πš…π™΄π™²πšƒπ™Ύπš)
Restrictions
π™½πš…π™΄π™²β‰₯0
π™½πš…π™΄π™²β‰€|πš…π™΄π™²πšƒπ™Ύπšπš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(πš…π™΄π™²πšƒπ™Ύπšπš‚,𝚟𝚎𝚌)
Purpose

The number of distinct tuples of values taken by the vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ is greater than or equal to π™½πš…π™΄π™². Two tuples of values 〈A 1 ,A 2 ,...,A m βŒͺ and 〈B 1 ,B 2 ,...,B m βŒͺ are distinct if and only if there exist an integer i∈[1,m] such that A i β‰ B i .

Example
2,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-9,3,𝚟𝚎𝚌-5,6,𝚟𝚎𝚌-9,4

The πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš› constraint holds since the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ involves at least 2 distinct tuples of values (i.e.,Β in fact the 3 distinct tuples 〈5,6βŒͺ, 〈9,3βŒͺ and 〈9,4βŒͺ).

Typical
π™½πš…π™΄π™²>1
π™½πš…π™΄π™²<|πš…π™΄π™²πšƒπ™Ύπšπš‚|
|πš…π™΄π™²πšƒπ™Ύπš|>1
|πš…π™΄π™²πšƒπ™Ύπšπš‚|>1
Symmetries
  • π™½πš…π™΄π™² can be decreased to any value β‰₯0.

  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚ are permutable.

  • Items of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 are permutable (same permutation used).

  • All occurrences of two distinct tuples of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be swapped; all occurrences of a tuple of values of πš…π™΄π™²πšƒπ™Ύπšπš‚.𝚟𝚎𝚌 can be renamed to any unused tuple of values.

Reformulation

By introducing an extra variable π™½πš…βˆˆ[0,|πš…π™΄π™²πšƒπ™Ύπšπš‚|], the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›(π™½πš…,πš…π™΄π™²πšƒπ™Ύπšπš‚) constraint can be expressed in term of an πš—πšŸπšŽπšŒπšπš˜πš›(π™½πš…,πš…π™΄π™²πšƒπ™Ύπšπš‚) constraint and of an inequality constraint π™½πš…β‰₯π™½πš…π™΄π™².

See also

comparison swapped: πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›.

generalisation: πš—πšŸπšŽπšŒπšπš˜πš›Β (β‰₯ π™½πš…π™΄π™² replaced by = π™½πš…π™΄π™²).

implied by: πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš›.

used in graph description: πš•πšŽπš‘_πšŽπššπšžπšŠπš•.

Keywords

characteristic of a constraint: vector.

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes.

problems: domination.

Arc input(s)

πš…π™΄π™²πšƒπ™Ύπšπš‚

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

Arc arity
Arc constraint(s)
πš•πšŽπš‘_πšŽπššπšžπšŠπš•(πšŸπšŽπšŒπšπš˜πš›πšœ1.𝚟𝚎𝚌,πšŸπšŽπšŒπšπš˜πš›πšœ2.𝚟𝚎𝚌)
Graph property(ies)
𝐍𝐒𝐂𝐂β‰₯π™½πš…π™΄π™²

Graph class
π™΄πš€πš„π™Έπš…π™°π™»π™΄π™½π™²π™΄

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.31.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐒𝐂𝐂 graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a tuple of values that is assigned to some vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection. The 3 following tuple of values 〈5,6βŒͺ, 〈9,3βŒͺ and 〈9,4βŒͺ are used by the vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection.

Figure 5.31.1. Initial and final graph of the πšŠπšπš•πšŽπšŠπšœπš_πš—πšŸπšŽπšŒπšπš˜πš› constraint
ctrs/atleast_nvectorActrs/atleast_nvectorB
(a) (b)