Global Constraint Catalog: Copen

5.301. open_minimum

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$

Constraint

$𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖 (𝙼𝙸𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, [𝚟𝚊𝚛, 𝚋𝚘𝚘𝚕])

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚋𝚘𝚘𝚕 \geq 0

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚋𝚘𝚘𝚕 \leq 1

Purpose

$𝙼𝙸𝙽$ is the minimum value of the variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚟𝚊𝚛$ , $(1 \leq i \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)$ for which $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚋𝚘𝚘𝚕 = 1$ (at least one of the Boolean variables is set to 1).

Example

(\begin{matrix} 3, 〈\begin{matrix} 𝚟𝚊𝚛 - 3 & 𝚋𝚘𝚘𝚕 - 1, \\ 𝚟𝚊𝚛 - 1 & 𝚋𝚘𝚘𝚕 - 0, \\ 𝚟𝚊𝚛 - 7 & 𝚋𝚘𝚘𝚕 - 0, \\ 𝚟𝚊𝚛 - 5 & 𝚋𝚘𝚘𝚕 - 1, \\ 𝚟𝚊𝚛 - 5 & 𝚋𝚘𝚘𝚕 - 1 \end{matrix}〉 \end{matrix})

The $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint holds since its first argument $𝙼𝙸𝙽 = 3$ is set to the minimum value of values $3, 1, 7, 5, 5$ for which the corresponding Boolean $1, 0, 0, 1, 1$ is set to 1 (i.e., values $3, 5, 5$ ).

Typical

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

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
One and the same constant can be added to $𝙼𝙸𝙽$ as well as to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Remark

The $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint is used in the reformulation of the $𝚝𝚛𝚎𝚎_𝚛𝚊𝚗𝚐𝚎$ constraint.

hard version: $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ .

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

uses in its reformulation: $𝚝𝚛𝚎𝚎_𝚛𝚊𝚗𝚐𝚎$ .

Keywords

characteristic of a constraint: minimum, automaton, automaton without counters, reified automaton constraint.

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

constraint type: order constraint, open constraint, open automaton constraint.

Automaton: Figure 5.301.1 depicts the automaton associated with the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint. Let ${𝚅𝙰𝚁}_{i}, 𝙱_{i}$ be the $i^{t h}$ item of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. To each triple $(𝙼𝙸𝙽, {𝚅𝙰𝚁}_{i}, 𝙱_{i})$ corresponds a signature variable $S_{i}$ as well as the following signature constraint: $(𝙱_{i} = 1 \land 𝙼𝙸𝙽 < {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 0) \land (𝙱_{i} = 1 \land 𝙼𝙸𝙽 = {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 1) \land (𝙱_{i} = 1 \land 𝙼𝙸𝙽 > {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 2) \land (𝙱_{i} = 0 \land 𝙼𝙸𝙽 < {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 3) \land (𝙱_{i} = 0 \land 𝙼𝙸𝙽 = {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 4) \land (𝙱_{i} = 0 \land 𝙼𝙸𝙽 > {𝚅𝙰𝚁}_{i} \Leftrightarrow S_{i} = 5)$ .

Figure 5.301.1. Automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint

Figure 5.301.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.301. open_minimum

Figure 5.301.1. Automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint

Figure 5.301.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.301. open_minimum

Figure 5.301.1. Automaton of the 𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖 constraint

Figure 5.301.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖 constraint

Figure 5.301.1. Automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint

Figure 5.301.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚘𝚙𝚎𝚗_𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ constraint