Global Constraint Catalog: Cin

5.177. in

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Domain definition.

Constraint

$𝚒𝚗 (𝚅𝙰𝚁, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Synonyms

$𝚍𝚘𝚖$ , $𝚒𝚗_𝚜𝚎𝚝$ , $𝚖𝚎𝚖𝚋𝚎𝚛$ .

Arguments

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

Restrictions

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

Purpose

Enforce the domain variable $𝚅𝙰𝚁$ to take a value within the values described by the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection.

Example

(3, 〈1, 3〉)

The $𝚒𝚗$ constraint holds since its first argument $𝚅𝙰𝚁 = 3$ occurs within the collection of values $𝚅𝙰𝙻𝚄𝙴𝚂 = 〈 1, 3 〉$ .

Typical

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

Symmetries

Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
$𝚅𝙰𝚁$ can be set to any value of $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ .
One and the same constant can be added to $𝚅𝙰𝚁$ as well as to the $𝚟𝚊𝚕$ attribute of all items of $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Arg. properties

Extensible wrt. $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Remark

Entailment occurs immediately after posting this constraint.

The $𝚒𝚗$ constraint is called $𝚍𝚘𝚖$ in Gecode (http://www.gecode.org/), and $𝚖𝚎𝚖𝚋𝚎𝚛$ in MiniZinc (http://www.minizinc.org/). In MiniZinc the $𝚟𝚊𝚕$ attribute is not necessarily fixed, i.e. it can be a domain variable.

Systems

member in Choco, rel in Gecode, dom in Gecode, in in JaCoP, member in MiniZinc, in in SICStus, in_set in SICStus.

Used in

$𝚊𝚖𝚘𝚗𝚐$ , $𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚊𝚝𝚖𝚘𝚜𝚝_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ , $𝚐𝚛𝚘𝚞𝚙$ , $𝚐𝚛𝚘𝚞𝚙_𝚜𝚔𝚒𝚙_𝚒𝚜𝚘𝚕𝚊𝚝𝚎𝚍_𝚒𝚝𝚎𝚖$ , $𝚒𝚗_𝚜𝚊𝚖𝚎_𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ , $𝚘𝚙𝚎𝚗_𝚊𝚖𝚘𝚗𝚐$ .

implied by: $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ , $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ .

implies: $𝚋𝚎𝚝𝚠𝚎𝚎𝚗_𝚖𝚒𝚗_𝚖𝚊𝚡$ .

negation: $𝚗𝚘𝚝_𝚒𝚗$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: unary constraint.

constraint network structure: centered cyclic(1) constraint network(1).

constraint type: value constraint.

filtering: arc-consistency.

modelling: included, domain definition.

Derived Collection

𝚌𝚘𝚕 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), [𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚅𝙰𝚁)])

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ $𝚅𝙰𝙻𝚄𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕

Graph property(ies)

𝐍𝐀𝐑𝐂

= 1

Graph model

Parts (A) and (B) of Figure 5.177.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the unique arc of the final graph is stressed in bold.

Figure 5.177.1. Initial and final graph of the $𝚒𝚗$ constraint


(a)	(b)

Signature

Since all the $𝚟𝚊𝚕$ attributes of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection are distinct and because of the arc constraint $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 . 𝚟𝚊𝚛 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕$ the final graph contains at most one arc. Therefore we can rewrite $𝐍𝐀𝐑𝐂 = 1$ to $𝐍𝐀𝐑𝐂 \geq 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton: Figure 5.177.2 depicts the automaton associated with the $𝚒𝚗$ constraint. Let ${𝚅𝙰𝙻}_{i}$ be the $𝚟𝚊𝚕$ attribute of the $i^{t h}$ item of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection. To each pair $(𝚅𝙰𝚁, {𝚅𝙰𝙻}_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $𝚅𝙰𝚁 = {𝚅𝙰𝙻}_{i} \Leftrightarrow S_{i}$ .

Figure 5.177.2. Automaton of the $𝚒𝚗$ constraint

Figure 5.177.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.177. in

Figure 5.177.1. Initial and final graph of the $𝚒𝚗$ constraint

Figure 5.177.2. Automaton of the $𝚒𝚗$ constraint

Figure 5.177.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.177. in

Figure 5.177.1. Initial and final graph of the 𝚒𝚗 constraint

Figure 5.177.2. Automaton of the 𝚒𝚗 constraint

Figure 5.177.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚒𝚗 constraint

Figure 5.177.1. Initial and final graph of the $𝚒𝚗$ constraint

Figure 5.177.2. Automaton of the $𝚒𝚗$ constraint

Figure 5.177.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗$ constraint