Global Constraint Catalog: Cor

5.303. or

DESCRIPTION

LINKS

AUTOMATON

Origin

Logic

Constraint

$𝚘𝚛 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonym

$𝚛𝚎𝚕$ .

Arguments

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

Restrictions

𝚅𝙰𝚁 \geq 0

𝚅𝙰𝚁 \leq 1

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 2

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \geq 0

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \leq 1

Purpose

Let $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ be a collection of 0-1 variables ${𝚅𝙰𝚁}_{1}, {𝚅𝙰𝚁}_{2}, \dots, {𝚅𝙰𝚁}_{n}$ $(n \geq 2)$ . Enforce $𝚅𝙰𝚁 = {𝚅𝙰𝚁}_{1} \lor {𝚅𝙰𝚁}_{2} \lor \dots \lor {𝚅𝙰𝚁}_{n}$ .

Example

(0, 〈0, 0〉)

(1, 〈0, 1〉)

(1, 〈1, 0〉)

(1, 〈1, 1〉)

(1, 〈1, 0, 1〉)

Symmetry

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.

Arg. properties

Functional dependency: $𝚅𝙰𝚁$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 0$ .
Extensible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝚅𝙰𝚁 = 1$ .
Aggregate: $𝚅𝙰𝚁 (\lor)$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 (𝚞𝚗𝚒𝚘𝚗)$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	4	8	16	32	64	128	256

Number of solutions for $𝚘𝚛$ : domains $0 . . n$

ctrs/or-1-tikz

ctrs/or-2-tikz

Length (

n

)

Total

128

256

Parameter

value

127

255

Solution count for $𝚘𝚛$ : domains $0 . . n$

ctrs/or-3-tikz

ctrs/or-4-tikz

Systems

reifiedOr in Choco, rel in Gecode, orbool in JaCoP, #\/ in SICStus.

implies: $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ , $𝚖𝚊𝚡𝚒𝚖𝚞𝚖$ .

Keywords

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

constraint arguments: pure functional dependency.

constraint network structure: Berge-acyclic constraint network.

constraint type: Boolean constraint.

filtering: arc-consistency.

modelling: disjunction, functional dependency.

Cond. implications

$•$ $𝚘𝚛 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 2$

implies $𝚜𝚘𝚖𝚎_𝚎𝚚𝚞𝚊𝚕$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

$•$ $𝚘𝚛 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $𝚅𝙰𝚁 = 0$

implies $𝚗𝚘𝚛$ $(𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

when $𝚅𝙰𝚁 = 1$ .

$•$ $𝚘𝚛 (𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $𝚅𝙰𝚁 = 1$

implies $𝚗𝚘𝚛$ $(𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

when $𝚅𝙰𝚁 = 0$ .

Automaton

Figure 5.303.1 depicts a first deterministic automaton without counter associated with the $𝚘𝚛$ constraint. To the first argument $𝚅𝙰𝚁$ of the $𝚘𝚛$ constraint corresponds the first signature variable. To each variable ${𝚅𝙰𝚁}_{i}$ of the second argument $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ of the $𝚘𝚛$ constraint corresponds the next signature variable. There is no signature constraint.

Figure 5.303.1. Counter free automaton of the $𝚘𝚛$ constraint

Figure 5.303.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚘𝚛$ constraint

Figure 5.303.3 depicts a second deterministic automaton with one counter associated with the $𝚘𝚛$ constraint, where the argument $𝚅𝙰𝚁$ is unified to the final value of the counter.

Figure 5.303.3. Automaton (with one counter) of the $𝚘𝚛$ constraint

Figure 5.303.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝚘𝚛$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.303. or

Figure 5.303.1. Counter free automaton of the 𝚘𝚛 constraint

Figure 5.303.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚘𝚛 constraint

Figure 5.303.3. Automaton (with one counter) of the 𝚘𝚛 constraint

Figure 5.303.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the 𝚘𝚛 constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )

Figure 5.303.1. Counter free automaton of the $𝚘𝚛$ constraint

Figure 5.303.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚘𝚛$ constraint

Figure 5.303.3. Automaton (with one counter) of the $𝚘𝚛$ constraint

Figure 5.303.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝚘𝚛$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )