Global Constraint Catalog: Copen

5.295. open_among

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚊𝚖𝚘𝚗𝚐$ and $𝚘𝚙𝚎𝚗_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢$ .

Constraint

$𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐 (𝚂, 𝙽𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Arguments

$𝚂$	$𝚜𝚟𝚊𝚛$
$𝙽𝚅𝙰𝚁$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)$

Restrictions

𝚂 \geq 1

𝚂 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙽𝚅𝙰𝚁 \geq 0

𝙽𝚅𝙰𝚁 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

Purpose

Let $𝒱$ be the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ for which the corresponding position belongs to the set $𝚂$ . Positions are numbered from 1. $𝙽𝚅𝙰𝚁$ is the number of variables of $𝒱$ that take their value in $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Example

({2, 3, 4, 5}, 3, 〈8, 5, 5, 4, 1〉, 〈1, 5, 8〉)

The $𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐$ constraint holds since within the last four values (i.e., $𝚂 = {2, 3, 4, 5}$ ) of $〈 8, 5, 5, 4, 1 〉$ exactly 3 values belong to the set of values ${1, 5, 8}$ .

Typical

𝙽𝚅𝙰𝚁 > 0

𝙽𝚅𝙰𝚁 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > | 𝚅𝙰𝙻𝚄𝙴𝚂 |

Symmetries

Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that belongs to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ (resp. does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ ) can be replaced by any other value in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ (resp. not in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ ).

Arg. properties

Functional dependency: $𝙽𝚅𝙰𝚁$ determined by $𝚂$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝚁 = 0$ .

hard version: $𝚊𝚖𝚘𝚗𝚐$ .

used in graph description: $𝚒𝚗_𝚜𝚎𝚝$ .

Keywords

constraint arguments: constraint involving set variables.

constraint type: open constraint, value constraint, counting constraint.

modelling: functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑆𝐸𝐿𝐹

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜)

Arc arity

Arc constraint(s)

•

𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)

•

𝚒𝚗_𝚜𝚎𝚝

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚔𝚎𝚢, 𝚂)

Graph property(ies)

𝐍𝐀𝐑𝐂

= 𝙽𝚅𝙰𝚁

Graph model

The arc constraint corresponds to the conjunction of unary constraints $𝚒𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)$ and $𝚒𝚗_𝚜𝚎𝚝 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚔𝚎𝚢, 𝚂)$ defined in this catalogue. Consequently we employ the $𝑆𝐸𝐿𝐹$ arc generator in order to produce an initial graph with a single loop on each vertex.

Parts (A) and (B) of Figure 5.295.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.295.1. Initial and final graph of the $𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.295. open_among

Figure 5.295.1. Initial and final graph of the 𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐 constraint

Figure 5.295.1. Initial and final graph of the $𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐$ constraint