5.240. open_alldifferent

Origin

[HoeveRegin06]

Constraint

open_alldifferent​(S,​VARIABLES)​

Synonym(s)

open_alldiff, open_alldistinct, open_distinct.

Argument(s)

S	svar
VARIABLES	collection​(var−dvar)​

Restriction(s)

S≥1

S≤|VARIABLES|

required​(VARIABLES,​var)​

Purpose

Let V be the variables of the collection VARIABLES for which the corresponding position belongs to the set S. Enforce all variables of V to take distinct values.

Example

​(​{2,​3,​4}​,​〈9,​1,​9,​3〉)​

The open_alldifferent constraint holds since the last three (i.e., S=​{2,​3,​4}​) values of the collection 〈9,​1,​9,​3〉 are distinct.

Usage

In their article [HoeveRegin06], W.-J. van Hoeve and J.-C. Régin motivate the open_alldifferent constraint by the following scheduling problem. Consider a set of activities (where each activity has a fixed duration 1 and a start variable) that can be processed on two factory lines such that all the activities that will be processed on a given line must be pairwise distinct. This can be modelled by using one open open_alldifferent constraint for each line, involving all the start variables as well as a set variable whose final value specifies the set of activities assigned to that specific factory line.

Algorithm

A slight adaptation of the flow model that handles the original global_cardinality constraint [Regin96] is described in [HoeveRegin06].

See also

alldifferent, size_maximal_starting_sequence_alldifferent, open_global_cardinality, open_global_cardinality_low_up.

Key words

characteristic of a constraint: all different, disequality.

constraint arguments: constraint involving set variables.

constraint type: open constraint, value constraint.

filtering: flow.

Arc input(s)

VARIABLES

Arc generator

CLIQUE↦collection​(variables1,​variables2)​

Arc arity

2

Arc constraint(s)

• variables1.var=variables2.var

• in_set​(variables1.key,​S)​

• in_set​(variables2.key,​S)​

Graph property(ies)

MAX_NSCC≤1

Graph class

ONE_SUCC

---

Graph model

We generate a clique with an equality constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed one. Variables for which the corresponding position does not belong to the set S are removed from the final graph by the second and third conditions of the arc -constraint.

Parts (A) and (B) of Figure 5.240.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 open_alldifferent holds since all the strongly connected components have at most one vertex: a value is used at most once.

Figure 5.240.1. Initial and final graph of the open_alldifferent constraint

(a)	(b)