5.9. alldifferent_except_0

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πšŠπš•πš•πšπš’πšπš_πšŽπš‘πšŒπšŽπš™πš_0, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πšŽπš‘πšŒπšŽπš™πš_0.

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restriction
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Enforce all variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to take distinct values, except those variables that are assigned value 0.

Example
πšŸπšŠπš›-5,πšŸπšŠπš›-0,πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-0,πšŸπšŠπš›-3

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint holds since all the values (that are different from 0) 5, 1, 9 and 3 are distinct.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
πšŠπšπš•πšŽπšŠπšœπš(1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,0)
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • Two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that are both different from 0 can be swapped; a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that is different from 0 can be renamed to any unused value that is also different from 0.

Usage

Quite often it appears that, for some modelling reason, you create a joker value. You do not want that normal constraints hold for variables that take this joker value. For this purpose we modify the binary arc constraint in order to discard the vertices for which the corresponding variables are assigned value 0. This will be effectively the case since all the corresponding arcs constraints will not hold.

See also

cost variant: πš πšŽπš’πšπš‘πšπšŽπš_πš™πšŠπš›πšπš’πšŠπš•_πšŠπš•πš•πšπš’πšπš.

hard version: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

implied by: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

characteristic of a constraint: joker value, all different, automaton, automaton with array of counters.

constraint type: value constraint, relaxation.

filtering: arc-consistency.

final graph structure: one_succ.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰ 0
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

Graph model

The graph model is the same as the one used for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, except that we discard all variables that are assigned value 0.

PartsΒ (A) andΒ (B) of FigureΒ 5.9.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph. The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 holds since all the strongly connected components have at most one vertex: a value different from 0 is used at most once.

Figure 5.9.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint
ctrs/alldifferent_except_0Actrs/alldifferent_except_0B
(a) (b)
Automaton

FigureΒ 5.9.2 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i and πš‚ i : πš…π™°πš i β‰ 0β‡”πš‚ i . The automaton counts the number of occurrences of each value different from 0 and finally imposes that each non-zero value is taken at most one time.

Figure 5.9.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0 constraint
ctrs/alldifferent_except_01