Global Constraint Catalog: Cset_value

5.344. set_value_precede

DESCRIPTION

LINKS

Origin

Constraint

$𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎 (𝚂, 𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝚂 \neq 𝚃

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

If there exists a set variable $v_{1}$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ such that $𝚂$ does not belong to $v_{1}$ and $𝚃$ does, then there also exists a set variable $v_{2}$ preceding $v_{1}$ such that $𝚂$ belongs to $v_{2}$ and $𝚃$ does not.

Example

(2, 1, 〈𝚟𝚊𝚛 - {0, 2}, 𝚟𝚊𝚛 - {0, 1}, 𝚟𝚊𝚛 - \emptyset, 𝚟𝚊𝚛 - {1}〉)

(0, 1, 〈𝚟𝚊𝚛 - {0, 2}, 𝚟𝚊𝚛 - {0, 1}, 𝚟𝚊𝚛 - \emptyset, 𝚟𝚊𝚛 - {1}〉)

(0, 2, 〈𝚟𝚊𝚛 - {0, 2}, 𝚟𝚊𝚛 - {0, 1}, 𝚟𝚊𝚛 - \emptyset, 𝚟𝚊𝚛 - {1}〉)

(0, 4, 〈𝚟𝚊𝚛 - {0, 2}, 𝚟𝚊𝚛 - {0, 1}, 𝚟𝚊𝚛 - \emptyset, 𝚟𝚊𝚛 - {1}〉)

The following examples are taken from [Law05]:

The $𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ $(2, 1, 〈 {0, 2}, {0, 1}, {}, {1} 〉)$ constraint holds since the first occurrence of value 2 precedes the first occurrence of value 1 (i.e., the set ${0, 2}$ occurs before the set ${0, 1}$ ).
The $𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ $(0, 1, 〈 {0, 2}, {0, 1}, {}, {1} 〉)$ constraint holds since the first occurrence of value 0 precedes the first occurrence of value 1 (i.e., the set ${0, 2}$ occurs before the set ${0, 1}$ ).
The $𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ $(0, 2, 〈 {0, 2}, {0, 1}, {}, {1} 〉)$ constraint holds since “there is no set in $〈 {0, 2}, {0, 1}, {}, {1} 〉$ that contains 2 but not 0”.
The $𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ $(0, 4, 〈 {0, 2}, {0, 1}, {}, {1} 〉)$ constraint holds since no set in $〈 {0, 2}, {0, 1}, {}, {1} 〉$ contains value 4.

Typical

𝚂 < 𝚃

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

Arg. properties

Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Algorithm

A filtering algorithm for maintaining value precedence on a sequence of set variables is presented in [YatChiuLawJimmyLee04]. Its complexity is linear to the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Systems

precede in Gecode.

See also

specialisation: $𝚒𝚗𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ ( $𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ of $𝚜𝚎𝚝 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ replaced by $𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ of $𝚍𝚘𝚖𝚊𝚒𝚗 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

Keywords

constraint arguments: constraint involving set variables.

constraint type: order constraint.

symmetry: symmetry, indistinguishable values, value precedence.

Global Constraint Catalog

5. Global Constraint Catalogue

5.344. set_value_precede