5.247. open_atmost

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšŠπšπš–πš˜πšœπš and πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’.

Constraint

πš˜πš™πšŽπš—_πšŠπšπš–πš˜πšœπš(πš‚,𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄)

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

Let 𝒱 be the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ for which the corresponding position belongs to the set πš‚. Positions are numbered from 1. At most 𝙽 variables of 𝒱 are assigned value πš…π™°π™»πš„π™΄.

Example
{2,3,4},1,2,2,4,5,2

The πš˜πš™πšŽπš—_πšŠπšπš–πš˜πšœπš constraint holds since, within the last three (i.e.,Β πš‚={2,3,4}) values of the collection 〈2,2,4,5βŒͺ, at most 𝙽=1 value is equal to value πš…π™°π™»πš„π™΄=2.

Symmetries
  • 𝙽 can be increased.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be replaced by any other value that is different from πš…π™°π™»πš„π™΄.

See also

common keyword: πš˜πš™πšŽπš—_πšŠπš–πš˜πš—πš, πš˜πš™πšŽπš—_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (open constraint,value constraint).

comparison swapped: πš˜πš™πšŽπš—_πšŠπšπš•πšŽπšŠπšœπš.

hard version: πšŠπšπš–πš˜πšœπš.

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint arguments: constraint involving set variables.

constraint type: open constraint, value constraint.

modelling: at most.

Arc input(s)

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

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πš…π™°π™»πš„π™΄
β€’ πš’πš—_𝚜𝚎𝚝(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πš”πšŽπš’,πš‚)
Graph property(ies)
𝐍𝐀𝐑𝐂≀𝙽

Graph model

Since each arc constraint involves only one vertex (πš…π™°π™»πš„π™΄ is fixed), we employ the 𝑆𝐸𝐿𝐹 arc generator in order to produce a graph with a single loop on each vertex. Variables for which the corresponding position does not belong to the set πš‚ are removed from the final graph by the second condition of the arc -constraint.

PartsΒ (A) andΒ (B) of FigureΒ 5.247.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the loops of the final graph are stressed in bold.

Figure 5.247.1. Initial and final graph of the πš˜πš™πšŽπš—_πšŠπšπš–πš˜πšœπš constraint
ctrs/open_atmostActrs/open_atmostB
(a) (b)