hide
Free keywords:
-
Abstract:
We present narrowing algorithms for the sortedness and the alldifferent
constraint which achieve bound-consistency.
The algorithm for the sortedness constraint takes as input $2n$ intervals $X_1,
\dots, X_n$, $Y_1, \dots, Y_n$ from a linearly ordered set $D$.
Let $\mathcal{S}$ denote the set of all tuples $t \in X_1 \times \cdots \times
X_n \times Y_1 \times \cdots \times Y_n$ such that the last $n$ components of
$t$ are obtained by sorting the first $n$ components. Our algorithm determines
whether $\mathcal{S}$ is non-empty and if so reduces the intervals to
bound-consistency. The running time of the algorithm is asymptotically the
same as for sorting the interval endpoints. In problems where this is faster
than $O(n \log n)$, this improves upon previous results.
The algorithm for the alldifferent constraint takes as input $n$ integer
intervals $Z_1, \dots, Z_n$. Let $\mathcal{T}$ denote all tuples $t \in Z_1
\times \cdots \times Z_n$ where all components are pairwise different. The
algorithm checks whether $\mathcal{T}$ is non-empty and if so reduces the
ranges to bound-consistency. The running time is also asymptotically the
same as for sorting the interval endpoints. When the constraint is for example
a permutation constraint, i.e. $Z_i \subseteq \range{1}{n}$ for all $i$, the
running time is linear. This also improves upon previous results.
