5.307. ordered_atmost_nvector

DESCRIPTIONLINKSGRAPH
Origin

Conjoin πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› and πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš.

Constraint

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

Synonyms

πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›πšœ, πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πš™πš˜πš’πš—πš, πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πš™πš˜πš’πš—πšπšœ.

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

Enforces the following two conditions:

  1. The number of distinct tuples of values taken by the vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ is less 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 .

  2. For each pair of consecutive vectors πš…π™΄π™²πšƒπ™Ύπš i and πš…π™΄π™²πšƒπ™Ύπš i+1 of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection we have that πš…π™΄π™²πšƒπ™Ύπš i is lexicographically less than or equal to πš…π™΄π™²πšƒπ™Ύπš i+1 . Given two vectors, X β†’ and Y β†’ of n components, 〈X 0 ,β‹―,X n-1 βŒͺ and 〈Y 0 ,β‹―,Y n-1 βŒͺ, X β†’ is lexicographically less than or equal to Y β†’ if and only if n=0 or X 0 <Y 0 or X 0 =Y 0 and 〈X 1 ,β‹―,X n-1 βŒͺ is lexicographically less than or equal to 〈Y 1 ,β‹―,Y n-1 βŒͺ.

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

The πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› constraint holds since:

  1. The collection πš…π™΄π™²πšƒπ™Ύπšπš‚ involves at most 3 distinct tuples of values (i.e.,Β in fact the 2 distinct tuples 〈5,6βŒͺ and 〈9,3βŒͺ).

  2. The vectors of the collection πš…π™΄π™²πšƒπ™Ύπšπš‚ are sorted in increasing lexicographical order.

Typical
|πš…π™΄π™²πšƒπ™Ύπš|>1
π™½πš…π™΄π™²>1
π™½πš…π™΄π™²<|πš…π™΄π™²πšƒπ™Ύπšπš‚|
|πš…π™΄π™²πšƒπ™Ύπšπš‚|>1
Symmetry

π™½πš…π™΄π™² can be increased.

Arg. properties

Contractible wrt. πš…π™΄π™²πšƒπ™Ύπšπš‚.

Reformulation

The πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› constraint can be reformulated as a conjunction of a πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› and a πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπšš constraints.

See also

common keyword: πš—πšŸπšŽπšŒπšπš˜πš›Β (vector).

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

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

implies: πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš›, πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœπšŽπššΒ (π™½πš…π™΄π™² of constraint πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› removed).

used in graph description: πš•πšŽπš‘_πš•πšŽπšœπšœ, πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš.

Keywords

characteristic of a constraint: vector.

constraint type: counting constraint, order constraint.

symmetry: symmetry.

Arc input(s)

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŽπšŒπšπš˜πš›πšœ1,πšŸπšŽπšŒπšπš˜πš›πšœ2)

Arc arity
Arc constraint(s)
πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš(πšŸπšŽπšŒπšπš˜πš›πšœ1.𝚟𝚎𝚌,πšŸπšŽπšŒπšπš˜πš›πšœ2.𝚟𝚎𝚌)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™΄π™²πšƒπ™Ύπšπš‚|-1

Arc input(s)

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŽπšŒπšπš˜πš›πšœ1,πšŸπšŽπšŒπšπš˜πš›πšœ2)

Arc arity
Arc constraint(s)
πš•πšŽπš‘_πš•πšŽπšœπšœ(πšŸπšŽπšŒπšπš˜πš›πšœ1.𝚟𝚎𝚌,πšŸπšŽπšŒπšπš˜πš›πšœ2.𝚟𝚎𝚌)
Graph property(ies)
ππ‚π‚β‰€π™½πš…π™΄π™²

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.307.1 respectively show the initial and final graph of the second graph constraint associated with the Example slot. Since we use the 𝐍𝐂𝐂 graph property in this second graph constraint, we show the different 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 2 following tuple of values 〈5,6βŒͺ and 〈9,3βŒͺ are used by the vectors of the πš…π™΄π™²πšƒπ™Ύπšπš‚ collection.

Figure 5.307.1. Initial and final graph of the πš˜πš›πšπšŽπš›πšŽπš_πšŠπšπš–πš˜πšœπš_πš—πšŸπšŽπšŒπšπš˜πš› constraint
ctrs/ordered_atmost_nvectorActrs/ordered_atmost_nvectorB
(a) (b)