5.235. not_in

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πš’πš—.

Constraint

πš—πš˜πš_πš’πš—(πš…π™°πš,πš…π™°π™»πš„π™΄πš‚)

Arguments
πš…π™°πšπšπšŸπšŠπš›
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
Purpose

Remove the values of the πš…π™°π™»πš„π™΄πš‚ collection from the domain variable πš…π™°πš.

Example
(2,1,3)

The constraint πš—πš˜πš_πš’πš— holds since the value of its first argument πš…π™°πš=2 does not occur within the collection 〈1,3βŒͺ.

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

Entailment occurs immediately after posting this constraint and removing all values in πš…π™°π™»πš„π™΄πš‚ from πš…π™°πš.

Systems

notMember in Choco, rel in Gecode.

Used in

πšπš›πš˜πšžπš™.

See also

negation: πš’πš—.

Keywords

characteristic of a constraint: disequality, 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, entailment.

modelling: excluded, domain definition.

Derived Collection
πšŒπš˜πš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),[πš’πšπšŽπš–(πšŸπšŠπš›-πš…π™°πš)])
Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ πš…π™°π™»πš„π™΄πš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•
Graph property(ies)
𝐍𝐀𝐑𝐂=0

Graph model

FigureΒ 5.235.1 shows the initial graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂=0 graph property the corresponding final graph is empty.

Figure 5.235.1. Initial graph of the πš—πš˜πš_πš’πš— constraint (the final graph is empty)
ctrs/not_inA
Signature

Since 0 is the smallest number of arcs of the final graph we can rewrite 𝐍𝐀𝐑𝐂=0 to 𝐍𝐀𝐑𝐂≀0. This leads to simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Μ².

Automaton

FigureΒ 5.235.2 depicts the automaton associated with the πš—πš˜πš_πš’πš— constraint. Let πš…π™°π™» i be the πšŸπšŠπš• attribute of the i th item of the πš…π™°π™»πš„π™΄πš‚ collection. To each pair (πš…π™°πš,πš…π™°π™» i ) corresponds a 0-1 signature variable πš‚ i as well as the following signature constraint: πš…π™°πš=πš…π™°π™» i β‡”πš‚ i .

Figure 5.235.2. Automaton of the πš—πš˜πš_πš’πš— constraint
ctrs/not_in1
Figure 5.235.3. Hypergraph of the reformulation corresponding to the automaton of the πš—πš˜πš_πš’πš— constraint
ctrs/not_in2