Global Constraint Catalog: Cdomain

5.136. domain_constraint

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Refalo00]

Constraint

$𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝 (𝚅𝙰𝚁, 𝚅𝙰𝙻𝚄𝙴𝚂)$

Synonym

$𝚍𝚘𝚖𝚊𝚒𝚗$ .

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, [𝚟𝚊𝚛 01, 𝚟𝚊𝚕𝚞𝚎])

𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚛 01 \geq 0

𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚛 01 \leq 1

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

Purpose

Make the link between a domain variable $𝚅𝙰𝚁$ and those 0-1 variables that are associated with each potential value of $𝚅𝙰𝚁$ : The 0-1 variable associated with the value that is taken by variable $𝚅𝙰𝚁$ is equal to 1, while the remaining 0-1 variables are all equal to 0.

Example

(\begin{matrix} 5, 〈\begin{matrix} 𝚟𝚊𝚛 01 - 0 & 𝚟𝚊𝚕𝚞𝚎 - 9, \\ 𝚟𝚊𝚛 01 - 1 & 𝚟𝚊𝚕𝚞𝚎 - 5, \\ 𝚟𝚊𝚛 01 - 0 & 𝚟𝚊𝚕𝚞𝚎 - 2, \\ 𝚟𝚊𝚛 01 - 0 & 𝚟𝚊𝚕𝚞𝚎 - 7 \end{matrix}〉 \end{matrix})

The $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ holds since $𝚅𝙰𝚁 = 5$ is set to the value corresponding to the 0-1 variable set to 1, while the other 0-1 variables are all set to 0.

Typical

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 1

Symmetry

Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.

Usage

This constraint is used in order to make the link between a formulation using finite domain constraints and a formulation exploiting 0-1 variables.

Reformulation

The $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ $(𝚅𝙰𝚁,$

$〈 𝚟𝚊𝚛 01 - B_{1} 𝚟𝚊𝚕𝚞𝚎 - v_{1},$

$𝚟𝚊𝚛 01 - B_{2} 𝚟𝚊𝚕𝚞𝚎 - v_{2},$

$\dots \dots \dots \dots \dots \dots \dots \dots$

$𝚟𝚊𝚛 01 - B_{| 𝚅𝙰𝙻𝚄𝙴𝚂 |} 𝚟𝚊𝚕𝚞𝚎 - v_{| 𝚅𝙰𝙻𝚄𝙴𝚂 |} 〉)$

constraint can be expressed in term of the following reified constraint $(𝚅𝙰𝚁 = v_{1} \land B_{1} = 1) \lor (𝚅𝙰𝚁 = v_{2} \land B_{2} = 1) \lor \dots \lor (𝚅𝙰𝚁 = v_{| 𝚅𝙰𝙻𝚄𝙴𝚂 |} \land B_{| 𝚅𝙰𝙻𝚄𝙴𝚂 |} = 1)$ .

Systems

domainChanneling in Choco, channel in Gecode, in in SICStus, in_set in SICStus.

related: $𝚛𝚘𝚘𝚝𝚜$ .

Keywords

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

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

constraint type: decomposition.

filtering: linear programming, arc-consistency.

modelling: channelling constraint, domain channel, Boolean channel.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝚅𝙰𝙻𝚄𝙴 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 01 - 𝚒𝚗𝚝, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 01 - 1, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝚁)] \end{matrix})

Arc input(s)

$𝚅𝙰𝙻𝚄𝙴$ $𝚅𝙰𝙻𝚄𝙴𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚕𝚞𝚎 . 𝚟𝚊𝚕𝚞𝚎 = 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚕𝚞𝚎 \Leftrightarrow 𝚟𝚊𝚕𝚞𝚎𝚜 . 𝚟𝚊𝚛 01 = 1

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙰𝙻𝚄𝙴𝚂 |

Graph model

The $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint is modelled with the following bipartite graph:

The first class of vertices corresponds to a single vertex containing the domain variable.
The second class of vertices contains one vertex for each item of the collection $𝚅𝙰𝙻𝚄𝙴𝚂$ .

$𝑃𝑅𝑂𝐷𝑈𝐶𝑇$ is used in order to generate the arcs of the graph. In our context it takes a collection with a single item $〈 𝚟𝚊𝚛 01 - 1 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝚁 〉$ and the collection $𝚅𝙰𝙻𝚄𝙴𝚂$ .

The arc constraint between the variable $𝚅𝙰𝚁$ and one potential value $v$ expresses the following:

If the 0-1 variable associated with $v$ is equal to 1, $𝚅𝙰𝚁$ is equal to $v$ .
Otherwise, if the 0-1 variable associated with $v$ is equal to 0, $𝚅𝙰𝚁$ is not equal to $v$ .

Since all arc constraints should hold the final graph contains exactly $| 𝚅𝙰𝙻𝚄𝙴𝚂 |$ arcs.

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

Figure 5.136.1. Initial and final graph of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint


(a)	(b)

Signature

Since the number of arcs of the initial graph is equal to $𝚅𝙰𝙻𝚄𝙴𝚂$ the maximum number of arcs of the final graph is also equal to $𝚅𝙰𝙻𝚄𝙴𝚂$ . Therefore we can rewrite the graph property $𝐍𝐀𝐑𝐂$ $=$ $| 𝚅𝙰𝙻𝚄𝙴𝚂 |$ to $𝐍𝐀𝐑𝐂$ $\geq$ $| 𝚅𝙰𝙻𝚄𝙴𝚂 |$ . This leads to simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton: Figure 5.136.2 depicts the automaton associated with the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint. Let $𝚅𝙰𝚁 01_{i}$ and ${𝚅𝙰𝙻𝚄𝙴}_{i}$ respectively be the $𝚟𝚊𝚛 01$ and the $𝚟𝚊𝚕𝚞𝚎$ attributes of the $i^{t h}$ item of the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection. To each triple $(𝚅𝙰𝚁, 𝚅𝙰𝚁 01_{i}, {𝚅𝙰𝙻𝚄𝙴}_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $((𝚅𝙰𝚁 = {𝚅𝙰𝙻𝚄𝙴}_{i}) \Leftrightarrow 𝚅𝙰𝚁 01_{i}) \Leftrightarrow S_{i}$ .

Figure 5.136.2. Automaton of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint

Figure 5.136.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint: since all states variables $Q_{0}, Q_{1}, \dots, Q_{n}$ are fixed to the unique state $s$ of the automaton, the transitions constraints involve only a single variable and the constraint network is Berge-acyclic

Global Constraint Catalog

5. Global Constraint Catalogue

5.136. domain_constraint

Figure 5.136.1. Initial and final graph of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint

Figure 5.136.2. Automaton of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.136. domain_constraint

Figure 5.136.1. Initial and final graph of the 𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝 constraint

Figure 5.136.2. Automaton of the 𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝 constraint

Figure 5.136.1. Initial and final graph of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint

Figure 5.136.2. Automaton of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint