5.8. alldifferent_except_0

Origin

Derived from alldifferent.

Constraint

alldifferent_except_0​(VARIABLES)​

Synonym(s)

alldiff_except_0, alldistinct_except_0.

Argument(s)

VARIABLES

collection​(var−dvar)​

Restriction(s)

required​(VARIABLES,​var)​

Purpose

Enforce all variables of the collection VARIABLES to take distinct values, except those variables that are assigned to 0.

Example

​(〈5,​0,​1,​9,​0,​3〉)​

The alldifferent_except_0 constraint holds since all the values (that are different from 0) 5, 1, 9 and 3 are distinct.

Usage

Quite often it appears that, for some modelling reason, you create a joker value. You don't 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 to 0. This will be effectively the case since all the corresponding arcs constraints will not hold.

See also

alldifferent, weighted_partial_alldiff.

Key words

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)

VARIABLES

Arc generator

CLIQUE↦collection​(variables1,​variables2)​

Arc arity

2

Arc constraint(s)

• variables1.var≠0

• variables1.var=variables2.var

Graph property(ies)

MAX_NSCC≤1

---

Graph model

The graph model is the same as the one used for the alldifferent constraint, except that we discard all variables that are assigned to 0.

Parts (A) and (B) of Figure 5.8.1 respectively show the initial and final graph associated with the Example slot. Since we use the MAX_NSCC graph property we show one of the largest strongly connected component of the final graph. The alldifferent_except_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.8.1. Initial and final graph of the alldifferent_except_0 constraint

(a)	(b)

Automaton

Figure 5.8.2 depicts the automaton associated with the alldifferent_except_0 constraint. To each variable VAR_i of the collection VARIABLES corresponds a 0-1 signature variable S_i. The following signature constraint links VAR_i and S_i: VAR_i≠0⇔S_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.8.2. Automaton of the alldifferent_except_0 constraint