Finite Domain Bounds Consistency Revisited
C.W.~Choi\footnote{Department of Computer Science and Engineering
Shatin
N.T.
Hong Kong SAR
W.~Harvey\footnote{IC-Parc
William Penney Laboratory
Imperial College London
Exhibition Road
J.H.M.~Lee\footnotemark[1]
P.~J.~Stuckey\footnote{NICTA Victoria Laboratory
Department of Computer Science \& Software Engineering
3010
A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with constraint propagation for pruning the search space. Constraint propagation is performed by propagators implementing a certain notion of consistency. Bounds consistency is the method of choice for building propagators for arithmetic constraints and several global constraints in the finite integer domain. However, there has been some confusion in the definition of bounds consistency. In this paper we clarify the differences and similarities among the three commonly used notions of bounds consistency.
technotes.tex
\documentclass{article}
%%AIJ%%\documentclass{elsart}

%%AIJ%%\usepackage{times}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{epsfig}
\usepackage{url}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{ex}[theorem]{Example}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newcommand{\qed}{\hspace{\stretch{1}}$\Box$}
\newenvironment{proof}{\begin{quote}\textbf{Proof:}}{\hfill\qed\end{quote}}
\newenvironment{example}{\begin{ex}\rm}{\hfill\qed\end{ex}}

%%AIJ%%\newcommand{\cal}[1]{\mathcal{#1}}
%%AIJ%%\newenvironment{theorem}{\begin{thm}}{\end{thm}}
%%AIJ%%\newenvironment{lemma}{\begin{lem}}{\end{lem}}
%%AIJ%%\newenvironment{definition}{\begin{defn}}{\end{defn}}
%%AIJ%%\newenvironment{proposition}{\begin{prop}}{\end{prop}}
%%AIJ%%\newenvironment{corollary}{\begin{cor}}{\end{cor}}
%%AIJ%%\newenvironment{proof}{\begin{pf}}{\qed\end{pf}}
%%AIJ%%\newenvironment{example}{\begin{exmp}}{\qed\end{exmp}}

%%AIJ%%\marginparwidth 40pt
%%AIJ%%\addtolength{\marginparsep}{5pt}
\pagestyle{plain}

\long\def\ignore#1{}

%\newcommand{\pjs}[1]{\marginpar{\scriptsize{{\bf pjs}\\#1}}}
%\newcommand{\jeff}[1]{\marginpar{\scriptsize{{\bf jeff}\\#1}}}
%\newcommand{\jl}[1]{\marginpar{\scriptsize{{\bf jl}\\#1}}}
%\newcommand{\wh}[1]{\marginpar{\scriptsize{{\bf wh}\\#1}}}
\long\def\pjs#1{}
\long\def\jeff#1{}
\long\def\jl#1{}
\long\def\wh#1{}

\newcommand{\vs}{}
\long\def\short#1{}
\long\def\noproofs#1{#1}
\long\def\noreified#1{}

\newcommand{\VV}{{\cal V}}
\newcommand{\ZZ}{{\cal Z}}
\newcommand{\RR}{{\cal R}}
\newcommand{\II}{{\cal I}}
\newcommand{\DD}{{\cal D}}
\newcommand{\bnd}{\mathit{bnd}}
\newcommand{\ibnd}{\mathit{zbnd}}
\newcommand{\rbnd}{\mathit{rbnd}}
\newcommand{\dbnd}{\mathit{dbnd}}
\newcommand{\ibrules}{\mathit{zbrules}}
\newcommand{\dbrules}{\mathit{dbrules}}
\newcommand{\bounds}{\mathit{rbrules}}
\newcommand{\ibounds}{bounds($\ZZ$)}
\newcommand{\rbounds}{bounds($\RR$)}
\newcommand{\dbounds}{bounds($\DD$)}
\newcommand{\Ibounds}{Bounds($\ZZ$)}
\newcommand{\Rbounds}{Bounds($\RR$)}
\newcommand{\Dbounds}{Bounds($\DD$)}
\newcommand{\reified}{\mathit{reified}}
\newcommand{\range}[2]{\left[\,#1\,..\,#2\,\right]}
\newcommand{\interval}[2]{\left[#1\mbox{---}#2\right]}
\newcommand{\rangeop}{\operatorname{range}}
\newcommand{\realcast}{\operatorname{real}}
\newcommand{\intcast}{\operatorname{integral}}
\newcommand{\bequiv}{\stackrel{b}{\equiv}}
\newcommand{\bsqsubseteq}{\stackrel{b}{\sqsubseteq}}
\newcommand{\gfp}{\textup{gfp}}
\newcommand{\solv}{\mathit{solv}}
\newcommand{\rules}{\mathit{drules}}
\newcommand{\iter}{\mathit{iter}}
\newcommand{\dom}{\mathit{dom}}
\newcommand{\rdom}{\mathit{rdom}}
\newcommand{\vars}{\mathit{vars}}
\newcommand{\cons}{\mathit{cons}}
\newcommand{\op}{\textup{op}}
\newcommand{\bigsqcap}{\mathop{\lower.1ex\hbox{\Large$\sqcap$}}}
\newcommand{\true}{\mathit{true}}
\newcommand{\false}{\mathit{false}}
\newcommand{\imp}{\mathit{imp}}
%\newcommand{\solns}{\mathit{solns}}
\newcommand{\Joinf}{\Join\!\!}
\newcommand{\BOX}[0]{$\Box$}
\newcommand{\rulearrow}[0]{\rightarrowtail}
\newcommand{\cperm}{\mbox{\upshape\ttfamily perm}}
\newcommand{\cbmap}{\mbox{\upshape\ttfamily bch}}
\newcommand{\init}{\mathit{init}}
\newcommand{\dnf}{\mathit{dnf}}
\newcommand{\lhs}{\mathit{lhs}}
\newcommand{\rhs}{\mathit{rhs}}
\newcommand{\chfn}{\diamondsuit}
\newcommand{\setc}{{\{\}}}
\newcommand{\card}{{||}}
\newcommand{\cvar}{\lambda}
\newcommand{\calldiff}{\mbox{\upshape\ttfamily alldifferent}}
\newcommand{\lin}{\mathit{lin}}
\newcommand{\bcc}{\mathit{bcc}}
\newcommand{\tl}{\mathit{top}}

\def\eclipse{{ECL$^i$PS$^e$}}

%%AIJ%%\journal{Artificial Intelligence}

\begin{document}

%%AIJ%%\begin{frontmatter}
%%AIJ%%Research Note\\
\title{Finite Domain Bounds Consistency Revisited}
\author{
C.W.~Choi\footnote{Department of Computer Science and Engineering,
The Chinese University of Hong Kong, Shatin, N.T., Hong Kong SAR, China.
Email: \texttt{\{cwchoi,jlee\}@cse.cuhk.edu.hk}}
\and 
W.~Harvey\footnote{IC-Parc, William Penney Laboratory, Imperial College London, Exhibition Road, London SW7 2AZ. Email: \texttt{wh@icparc.ic.ac.uk}} 
\and 
J.H.M.~Lee\footnotemark[1]
\and 
P.~J.~Stuckey\footnote{NICTA Victoria Laboratory, Department of Computer Science \& Software Engineering, University of Melbourne, 3010, Australia. Email: \texttt{pjs@cs.mu.oz.au}}
}
\date{\today}
\maketitle

%%AIJ%%\author[cuhk]{C.W.~Choi},
%%AIJ%%\ead{cwchoi@cse.cuhk.edu.hk}
%%AIJ%%\author[icparc]{W. Harvey},
%%AIJ%%\ead{wh@icparc.ic.ac.uk}
%%AIJ%%\author[cuhk]{J.H.M. Lee},
%%AIJ%%\ead{jlee@cse.cuhk.edu.hk}
%%AIJ%%\author[mu]{P. J. Stuckey}
%%AIJ%%\ead{pjs@cs.mu.oz.au}
%%AIJ%%\address[cuhk]{Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong SAR, China}
%%AIJ%%\address[icparc]{IC-Parc, William Penney Laboratory, Imperial College London, Exhibition Road, London SW7 2AZ, UK.}
%%AIJ%%\address[mu]{NICTA Victorian Laboratories, Department of Computer Science \& Software Engineering, University of Melbourne, 3010, Australia}

\begin{abstract}
A widely adopted approach to solving constraint satisfaction problems 
combines systematic tree search with constraint propagation
for pruning the search space. 
Constraint propagation is performed by propagators implementing a certain
notion of consistency.
Bounds consistency is the method of choice for
building propagators for arithmetic constraints 
and several global constraints in the finite integer domain.
However, there has been some confusion in the 
definition of bounds consistency.
In this paper we clarify the differences and similarities
among the three commonly used notions of bounds consistency.
\end{abstract}

%%AIJ%%\begin{keyword}
%%AIJ%%Bounds Consistency, Constraint Propagation
%%AIJ%%\end{keyword}
%%AIJ%%\end{frontmatter}

\section{Introduction}\label{sec:intro}

%\jeff{reworded a little}
Finite domain constraint programming combines 
backtracking tree search with constraint propagation
to solve {\em constraint satisfaction problems\/} (CSPs)~\cite{mackworth}.
This framework is realized in constraint programming systems, 
such as \eclipse{}~\cite{eclipse-intro}, SICStus Prolog~\cite{sics}
and ILOG Solver~\cite{solver52}, which 
have been successfully applied to many real-life industrial 
applications.

\emph{Constraint propagation}, based on local consistency algorithms, removes 
infeasible values from the domains of variables to reduce the
search space.
The origins of this technique in the Artificial Intelligence
field concentrated on consistency notions for
constraints with two or fewer variables.
The most successful consistency technique 
was \emph{arc consistency}~\cite{mackworth}
which ensures that for each constraint, every value in the domain
of one variable has a supporting value in the
domain of the other variable which satisfies the constraint.

Arc consistency can be naturally extended to
constraints of more than two variables. This
extension has been called \emph{generalized arc consistency}~\cite{gac4},
as well as \emph{domain consistency}~\cite{pdv2}
(which is the terminology we will use),
and \emph{hyper-arc consistency}~\cite{book}.
%\jeff{NP-complete or NP-hard?}
%\pjs{NP-hard that will do, we don't care if its NP-complete
%just that its hard to solve}
Checking domain consistency is NP-complete
even for linear equations, an important kind of constraint.

To avoid this problem, weaker forms of consistency were introduced
for handling constraints with large numbers of variables.
The most notable one for linear arithmetic constraints
has been \emph{bounds consistency} 
(sometimes called \emph{interval consistency}).
Unfortunately there are \emph{three} commonly used but \emph{incompatible}
definitions of bounds consistency in the literature.
This is confusing to practitioners in the 
design and implementation of efficient bounds consistency algorithms,
as well as for users of constraint programming system claiming to support
bounds consistency.
In this paper we clarify the three existing definitions of bounds consistency 
and the differences between them. 
We also gives conditions under which the definitions may coincide 
for certain constraints.

\section{Background}\label{sec:backgrounds}

In this paper we consider integer constraint solving
using constraint propagation.
Let $\ZZ$ denote the integers, and $\RR$ denote the reals.
Hence $\ZZ \models F$ denotes that the formula $F$
is universally true in the integers 
(that is when the constants,
functions and  variables
are interpreted in the integer domain).
Similarly $\RR \models F$ denotes that the formula $F$
is universally true in the reals.

We consider a given (finite) set of integer variables $\VV$,
which we shall sometimes interpret as real variables.
Each variable is associated with a finite set of possible values,
defined by the domain.
A \emph{domain} $D$ is a complete mapping 
from a set of variables $\VV$ to finite sets of integers.
We assume in this paper that $D(v)$ for all $v \in \VV$ are totally ordered.

A \emph{valuation} $\theta$ is a mapping of 
variables to values (integers or reals), written 
$\{x_1 \mapsto d_1, \ldots, x_n \mapsto d_n\}$.
Let $\vars$ be the function that returns the set of
variables appearing in an expression, constraint or valuation.
%\jeff{clarified things a bit}
Given an expression $e$, $\theta(e)$ is obtained by replacing 
each $v \in \vars(e)$ by $\theta(v)$ and calculating
the value of the resulting variable free expression.

In an abuse of notation, we define a valuation 
$\theta$ to be an element of a domain $D$, 
written $\theta \in D$, iff $\theta(v) \in \ZZ$ 
and $\theta(v) \in D(v)$ for all $v \in \vars(\theta)$.
%
We are interested in determining the infimums and supremums of
expressions with respect to some domain $D$.
Define the \emph{infimum} and \emph{supremum} of an 
expression $e$ with respect to a
domain $D$ as $\inf_D e = \inf\{ \theta(e) ~|~ \theta \in D\}$ 
and $\sup_D e = \sup\{ \theta(e) ~|~ \theta \in D\}$.
%
We also use \emph{range} notation: $\range{l}{u}$
denotes the set $\{ d \in \ZZ ~|~ l \leq d \leq u \}$ 
when $l$ and $u$ are integers.
A domain is a \emph{range domain} if $D(x)$ is a range for all $x$.
Let $D' = \rangeop(D)$ be the smallest range domain containing $D$, 
i.e.\ domain $D'(x) = \range{\inf_D x}{\sup_D x}$ for all $x \in \VV$.

A constraint places restriction on the allowable values for
a set of variables and is usually written in well understood 
mathematical syntax. More formally, a {\em constraint\/}  
$c$ is a relation expressed using available function and relation 
symbols in a specific constraint language.  
For the purpose of this paper, we assume the usual integer 
interpretation of arithmetic constraints and logical operators 
such as $\neg$, $\wedge$, $\vee$, $\Rightarrow$, and $\Leftrightarrow$.
%\jeff{reworded a little}
We call $\theta$ an \emph{integer solutions} of $c$ iff
$\vars(\theta) = \vars(c)$ and $\ZZ \models_\theta c$.
Similarly, we call $\theta$ a \emph{real solutions} of $c$ iff
$\vars(\theta) = \vars(c)$ and $\RR \models_\theta c$.
A \emph{constraint satisfaction problem} (CSP) consists 
of a set of constraints read as conjunction.

Constraint propagation enforcing domain consistency ensures that 
for each constraint $c$, every value in the domain of each variable
can be extended to an assignment satisfying $c$.

%\jeff{changed to the usual defn of domain consistency}
\begin{defn}\label{defn:dom}
A domain $D$ is \emph{domain consistent} for a constraint $c$
where $\vars(c) = \{x_1, \ldots, x_n\}$,
if for each variable $x_i, 1 \leq i \leq n$ and 
for each $d_i \in D(x_i)$ there exist
integers $d_j$ with $d_j \in D(x_j)$,
$ 1 \leq  j \leq n, j \neq i$ such that
$\theta = \{x_1 \mapsto d_1, \ldots, x_n \mapsto d_n\}$ is an 
integer solution of $c$.
\end{defn}

\begin{example} \label{ex:1}
Consider the constraint $c_{\lin}~~ \equiv ~~ x_1 = 3 x_2 + 5 x_3$.
The domain $D_0$ defined by 
$D_0(x_1) = \range{2}{7}$,  
$D_0(x_2) = \range{0}{2}$, and 
$D_0(x_3) = \range{-1}{2}$ is not domain consistent w.r.t.\ $c_{\lin}$.
But the domain $D_1$ defined by 
$D_1(x_1) = \{3,5,6\}$,  
$D_1(x_2) = \{0,1,2\}$, and 
$D_1(x_3) = \{0,1\}$ is domain consistent for $c_{\lin}$,
supported by the integer solutions
$\theta_1 = \{x_1 \mapsto 3, x_2 \mapsto 1, x_3 \mapsto 0\}$,
$\theta_2 = \{x_1 \mapsto 5, x_2 \mapsto 0, x_3 \mapsto 1\}$, and
$\theta_3 = \{x_1 \mapsto 6, x_2 \mapsto 2, x_3 \mapsto 0\}$.
\end{example}

\section{Different Notions of Bounds Consistency}\label{sec:bc}

The basis of bounds consistency is to relax the consistency requirement
to apply only to the lower and upper bounds of the domain of
each variable. 
There are three incompatible definitions of bounds consistency
used in the literature, all for constraints with finite integer domains.
The first and second definitions are based on \emph{integer} solutions,
while the third definition is based on \emph{real} solutions.

%\jeff{changed the sequence, from strongest to weakest}
\begin{defn}\label{defn:dbounds}
A domain $D$ is \emph{\dbounds{} consistent} for a constraint $c$
where $\vars(c) = \{x_1, \ldots, x_n\}$,
if for each variable $x_i, 1 \leq i \leq n$ and 
for each $d_i  \in \{\inf_D x_i, \sup_D x_i\}$ there exist
\textbf{integers} $\boldsymbol{d_j}$ with $\boldsymbol{d_j \in D(x_j)}$,
$ 1 \leq  j \leq n, j \neq i$ such that
$\theta = \{x_1 \mapsto d_1, \ldots, x_n \mapsto d_n\}$ is an 
\textbf{integer solution} of $c$.
\end{defn}

\begin{defn}\label{defn:ibounds}
A domain $D$ is \emph{\ibounds{} consistent} for a constraint $c$
where $\vars(c) = \{x_1, \ldots, x_n\}$,
if for each variable $x_i, 1 \leq i \leq n$ and 
for each $d_i  \in \{\inf_D x_i, \sup_D x_i\}$ there exist
\textbf{integers} $\boldsymbol{d_j}$ with 
$\boldsymbol{\inf_D x_j \leq d_j \leq \sup_D x_j}$,
$1 \leq  j \leq n, j \neq i$ such that
$\theta = \{x_1 \mapsto d_1, \ldots, x_n \mapsto d_n\}$ is an 
\textbf{integer solution} of $c$.
\end{defn}

\begin{defn}\label{defn:rbounds}
A domain $D$ is \emph{\rbounds{} consistent} for a constraint $c$
where $\vars(c) = \{x_1, \ldots, x_n\}$,
if for each variable $x_i, 1 \leq i \leq n$ and 
for each $d_i  \in \{\inf_D x_i, \sup_D x_i\}$ there exist
\textbf{real numbers} $\boldsymbol{d_j}$ with 
$\boldsymbol{\inf_D x_j \leq d_j \leq \sup_D x_j}$, 
$1 \leq  j \leq n, j \neq i$ such that
$\theta = \{x_1 \mapsto d_1, \ldots, x_n \mapsto d_n\}$ 
is a \textbf{real solution} of $c$.
\end{defn}

Definition~\ref{defn:dbounds} is used in for example for 
the two definitions in
Dechter~\cite[pages 73 \& 435]{rina-book};
Frisch \bgroup \em et al.\egroup~\cite{toby-cp02};
and implicitly in %~\cite{arnaud}.
Lallouet \bgroup \em et al.\egroup~\cite{arnaud}.
%
Definition~\ref{defn:ibounds} is far more widely used appearing in 
for example %~\cite{pdv2,puget-alldifferent,sum-diff,vanBeek-gcc,sics}.
{Van Hentenryck} \bgroup \em et al.\egroup~\cite{pdv2};
Puget~\cite{puget-alldifferent};
R{\'e}gin \& Rueher~\cite{sum-diff};
Quimper \bgroup \em et al.\egroup~\cite{vanBeek-gcc}; and
SICStus Prolog~\cite{sics}.
%
Definition~\ref{defn:rbounds} appears in for 
example %~\cite{book,SchulteStuckey-PPDP2001,warwick-joachim}
Marriott \& Stuckey~\cite{book};
Schulte \& Stuckey~\cite{SchulteStuckey-PPDP2001};
Harvey \& Schimpf~\cite{warwick-joachim}; and 
Zhang \& Yap~\cite{ZhangYap00}.
%
Apt~\cite{apt-book} gives both 
Definitions~\ref{defn:ibounds}~and~\ref{defn:rbounds}, 
calling the former interval consistency 
and the latter bounds consistency.

Let us now examine the differences of the definitions.
\jeff{defined stronger properly}
Consider two notions of consistency $\Omega$ and $\Pi$.
We say that $\Omega$ consistency is \emph{at least as strong as} 
$\Pi$ consistency iff, given any constraint $c$ and domain $D$, 
if $D$ is $\Omega$ consistent for $c$ then $D$ is $\Pi$ consistent
for $c$. We say that $\Omega$ consistency is \emph{stronger than}
$\Pi$ consistency iff $\Omega$ consistency is at least 
as strong as $\Pi$ consistency, but $\Pi$ consistency
is \emph{not} at least as strong as $\Omega$ consistency.
The following relationship between the three notions of bounds
consistency is clear from the definition.

%\jeff{added a proposition and simplified the examples}
\wh{For some domains the relationship is not strict, so don't claim it is}
\jeff{removed the words stringent condition}
\begin{proposition}\label{prop:bounds_impl}
\Dbounds{} consistency is \emph{stronger} %(a more stringent condition)
than \ibounds{} consistency,
which is stronger than \rbounds{} consistency.
\end{proposition}
%\pjs{Do we need a proof or proof sketch}
%\jeff{Added proof sketch}
%\wh{Added alternate proof}
%\jeff{fixed proof for strictness}
\noproofs{
\ignore{%%IGNORE
\begin{proof}
(Sketch) Essentially if a domain $D$ is \dbounds{} consistent
for a constraint $c$, then $D$ is also \ibounds{} consistent 
for $c$. Similarly if $D$ is \ibounds{} consistent for $c$,
$D$ is also \rbounds{} consistent for $c$.
\end{proof}
}%%IGNORE
\begin{proof}
For each of the notions of consistency, for each bound of each
variable a support must be found, i.e.\ an assignment of values
to each of the other variables.
For each of these other variables, 
let $S_{\DD}$, $S_{\ZZ}$, and $S_{\RR}$ be the set of allowed values to choose 
from for \dbounds{}, \ibounds{} and \rbounds{} consistency respectively.

From the definition, $S_{\DD} \subseteq S_{\ZZ}$,
thus having a support 
for \dbounds{} consistency implies having a
support for \ibounds{} consistency.
The reverse is not always true: see Example~\ref{ex:bounds}.
Hence, \dbounds{} consistency is stronger than \ibounds{} consistency.
Similarly, $S_{\ZZ} \subseteq S_{\RR}$,
so \ibounds{} consistency is stronger than
\rbounds{} consistency (see Example~\ref{ex:bounds} again for a case
that is \rbounds{} consistent but not \ibounds{} consistent).
\end{proof}
}%%NOPROOFS

\begin{example}\label{ex:bounds}
Consider the constraint $c_{\lin}$ from Example~\ref{ex:1}.
The domain $D_2$ defined by 
$D_2(x_1) = \{2,3,4,6,7\}$,  
$D_2(x_2) = \range{0}{2}$, and 
$D_2(x_3) = \range{0}{1}$
is \rbounds{} consistent
(but not \dbounds{} consistent nor \ibounds{} consistent)
w.r.t.\ $c_{\lin}$, 
supported by the real solutions 
$\{x_1 \mapsto 2, x_2 \mapsto 2/3, x_3 \mapsto 0\}$,
$\{x_1 \mapsto 7, x_2 \mapsto 2, x_3 \mapsto 1/5\}$,
$\{x_1 \mapsto 5, x_2 \mapsto 0, x_3 \mapsto 1\}$.

The domain $D_3$ defined by  
$D_3(x_1) = \{3,4,6\}$,  
$D_3(x_2) = \range{0}{2}$, and 
$D_3(x_3) =\range{0}{1}$ 
is \ibounds{} and \rbounds{} consistent 
(but not \dbounds{} consistent)
w.r.t.\ $c_{\lin}$.

The domain $D_4$ defined by 
$D_4(x_1) = \{3,4,6\}$,
$D_4(x_2) = \range{1}{2}$, and
$D_4(x_3) = \{0\}$
is \dbounds{}, \ibounds{} and \rbounds{} consistent 
w.r.t.\ $c_{\lin}$.
\end{example}

\ignore{
\begin{example}\label{ex:bc1}
Consider the constraint $c_{\lin}$
and domain $D_0$ from Example~\ref{ex:1}.
Then $D_0$ is \emph{not} \rbounds{} consistent with respect to $c_{\lin}$
since there is no real solution of $c_{\lin} \wedge x_3 = -1 \wedge
2 \leq x_1 \leq 7 \wedge 0 \leq x_2 \leq 2$.
Note that the domain $D_2$ where
$D_2(x_1) = \range{2}{7}$,  $D_2(x_2) = \range{0}{2}$, 
and $D_2(x_3) = \range{0}{1}$
is \emph{\rbounds{} consistent} with respect to $c_{\lin}$,
supported by the real solutions 
$\{x_1 \mapsto 2, x_2 \mapsto 2/3, x_3 \mapsto 0\}$,
$\{x_1 \mapsto 7, x_2 \mapsto 2, x_3 \mapsto 1/5\}$,
$\{x_1 \mapsto 5, x_2 \mapsto 0, x_3 \mapsto 1\}$.
\end{example}

If we consider the same constraint using \ibounds{} consistency,
we get a different (stronger) result.

\begin{example}\label{ex:bc2}
Consider the constraint $c_{\lin}$,
and the domain $D_2$ from Example~\ref{ex:bc1}.
Then $D_2$ is not
\ibounds{} consistent with respect to $c_{\lin}$.
Consider the lower bound of $x_1$. There is no integer solution
of $2 = 3 x_2 + 5 x_3$ where $x_2 \in \{0,1,2\}$ and $x_3 \in \{0,1\}$.
The domain $D_3$ defined by  
$D_3(x_1) = \{3,4,6\}$,  $D_3(x_2) = \range{0}{2}$, and 
$D_3(x_3) =\range{0}{1}$ 
is \ibounds{} consistent w.r.t.\ $c_{\lin}$ (cf. Example~\ref{ex:1}).
\end{example}

\Dbounds{} consistency is even stronger than \ibounds{} consistency.

\begin{example}\label{ex:bc3}
Consider the constraint $c_{\lin}$,
and the domain $D_3$ from Example~\ref{ex:bc2}.
Then $D_3$ is not \dbounds{} consistent with respect to $c_{\lin}$.
There is no integer solution $\theta \in D_3$ where $\theta(x_2) = 0$,
even though there is an integer 
solution $\theta = \{ x_1 \mapsto 5, x_2 \mapsto 0, x_3 \mapsto 1\}$ 
in $\rangeop(D_3)$.
The domain $D_4$ defined by 
$D_4(x_1) = \{3,4,6\}$,
$D_4(x_2) = \range{1}{2}$, and
$D_4(x_3) = \{0\}$
is \dbounds{} consistent w.r.t.\ $c_{\lin}$.
\end{example}
}

The relationship between the \ibounds{} and \dbounds{} consistency
is straightforward to explain.

\begin{proposition}\label{prop:ibdb}
$D$ is \ibounds{} consistent with $c$
iff $\rangeop(D)$ is \dbounds{} consistent with $c$.
%\hfill $\Box$
\end{proposition}

The second definition of bounds consistency 
in Dechter~\cite[page 435]{rina-book} 
works only with 
range domains.  By Proposition~\ref{prop:ibdb}, the definition
coincides with both \ibounds{} and \dbounds{} consistency.  
Similarly, Apt's~\cite{apt-book} interval consistency is also 
equivalent to \dbounds{} consistency.
%\jeff{add comments and example}
But in general, finite domain constraint solvers 
do not always operate on range domains, 
but rather use a mix of propagators implementing
different kinds of consistencies, both domain and bounds consistency.

\begin{example}
Consider the constraint $c_{\lin}$ and domain $D_3$ 
from Example~\ref{ex:bounds}. 
Now $\rangeop(D_3)$ is both \dbounds{} and \ibounds{} consistent 
with $c_{\lin}$.
%supported by the three solutions $\theta_1, \theta_2, \theta_3$ 
%shown in Example~\ref{ex:1}.
But, as noted in Example~\ref{ex:bounds},
$D_3$ is only \ibounds{} consistent but \emph{not} \dbounds{} 
consistent with $c_{\lin}$.
\end{example}

Both \rbounds{} and \ibounds{} consistency depend only
on the upper and lower bounds of the domains of the variables 
under consideration.

\begin{proposition}\label{prop:range}
For $\alpha = \RR$ or $\alpha = \ZZ$ and constraint $c$,
$D$ is bounds($\alpha$) consistent for $c$ 
iff $\rangeop(D)$ is bounds($\alpha$) consistent for $c$.
%\hfill $\Box$
\end{proposition}

This is not the case for \dbounds{} consistency, which
suggests that, strictly, it is not really a form of \emph{bounds consistency}.
Indeed, most existing implementations of bounds propagators 
make use of Proposition~\ref{prop:range}
to avoid reexecuting a bounds propagator unless the lower
or upper bound of a variable involved in the propagator changes.
%For the remainder of the paper, we will focus more on the 
%first two definitions.

%\jeff{changed the example}
\begin{example}\label{ex:gap}
Consider the constraint $c_{\lin}$ and domain $D_3$ 
from Example~\ref{ex:bounds} again.
Both $D_3$ and $\rangeop(D_3)$ are \ibounds{} and \rbounds{}
consistency with $c_{\lin}$, but only $\rangeop(D_3)$ is
\dbounds{} consistent with $c_{\lin}$.
\end{example}

%\wh{Reworded a little}
There are significant problems with the
stronger \ibounds{} (and \dbounds{}) consistency. 
In particular, for linear equations it is NP-complete to check
\ibounds{} (and \dbounds{}) consistency,
%\jeff{Is \rbounds{} for linear equations linear\cite{SchulteStuckey-PPDP2001} 
%or quadratic\cite{ZhangYap00}?}
while for \rbounds{} consistency it is only linear time
(e.g.\ see Schulte \& Stuckey~\cite{SchulteStuckey-PPDP2001}).
%The following result holds by reduction
%from the SUBSET SUM NP-complete problem~\cite{garey+johnson}.

\begin{proposition}\label{prop:nphard}
Checking \ibounds{}, \dbounds{}, or domain consistency
of a domain $D$ with a linear equality
$a_1 x_1 + \cdots a_n x_n = a_0$
where $\{a_0, \ldots, a_n\}$ are integer constants
and $\{x_1, \ldots, x_n\}$ are integer variables, is NP-complete.
\end{proposition}
\begin{proof}
%\jeff{fixed the proof and added example}
It is clear that this problem belongs to NP.
Next, we show that the SUBSET SUM NP-complete problem~\cite{clr}
is polynomial reducible to this problem.

%\jeff{Added alternate proof}
\ignore{%%IGNORE
The SUBSET SUM problem is: given a set of $n$ integers
$A = \{a_1, \ldots, a_n\}$ and a constant $a_{n+1}$, determine if there
is a set $S \subseteq A$ where 
$\sum \{ a_i ~|~ a_i \in S \wedge 1 \leq i \leq n\} = a_{n+1}$.
For each integers $a_i$ where $1 \leq i \leq n+1$ we associate an
integer variable $x_i$ with the domain $D$ defined by
$D(x_j) = \{0,1\}$ for all $1 \leq j \leq n$ and $D(x_{n+1}) = \{1\}$. 
Now, checking whether the linear equation
$c \equiv a_1 x_1 + \cdots + a_n x_n - a_{n+1} x_{n+1} = 0$
is domain consistent with domain $D$ for variable $x_{n+1}$ 
is to find a valuation $\theta \in D$
where $\theta(x_{n+1}) = 1$ such that $c$ is satisfied.
The valuation $\theta$ defines a set 
$S = \{ a_i ~|~ \theta(x_i) = 1 \wedge 1 \leq i \leq n \}$ where 
$\sum \{ a_i ~|~ a_i \in S \wedge 1 \leq i \leq n \} - a_{n+1} = 0$.
}%%IGNORE

In the subset sum problem, we are given a set of $n$ natural numbers
$A = \{a_1, \ldots, a_n\}$ and a target natural number $a_{n+1}$, and we
must determine whether or not there exists a subset $S \subseteq A$ where 
$\sum \{ a_i ~|~ a_i \in S \wedge 1 \leq i \leq n\} = a_{n+1}$.
For each integer $a_i$ where $1 \leq i \leq n+1$ we associate an
integer variable $x_i$ with the domain $D$ defined by $D(x_i) = \{0,1\}$.
We also introduce another integer variable $x_{n+2}$ where $D(x_{n+2}) = \{0,1\}$.
Now, the linear equation $c$ defined by
\[
a_1 x_1 + \cdots + a_n x_n - a_{n+1} x_{n+1} - (\sum_{i=1}^{n} a_i) x_{n+2} = 0
\]
has integer solutions:
\[
\begin{array}{c}
\{x_1 \mapsto 0, \ldots, x_n \mapsto 0, x_{n+1} \mapsto 0, x_{n+2} \mapsto 0\} \\
\{x_1 \mapsto 1, \ldots, x_n \mapsto 1, x_{n+1} \mapsto 0, x_{n+2} \mapsto 1\}
\end{array}
\]
\wh{Spelled out a few more steps in the proof}%
These two solutions exhibit that all domain elements for all variables have
support, with the exception of $x_{n+1} \mapsto 1$.
Thus, $D$ is domain consistent for $c$ iff there exists
a valuation $\theta \in D$ where $\theta(x_{n+1}) = 1$ that satisfies $c$.
Clearly we cannot have $\theta(x_{n+1}) = 1$ and $\theta(x_{n+2}) = 1$ (no
solution), so any such $\theta$ must have $\theta(x_{n+2}) = 0$.
Such a valuation, if it exists, defines a set 
$S = \{ a_i ~|~ \theta(x_i) = 1 \wedge 1 \leq i \leq n \}$ such that
$\sum \{ a_i ~|~ a_i \in S \wedge 1 \leq i \leq n \} = a_{n+1}$;
conversely, the existence of such a set implies a corresponding valuation.
Thus there exists a solution to the SUBSET SUM problem iff there exists a
solution of $c$ with $\theta(x_{n+1}) = 1$ and $\theta(x_{n+2}) = 0$, iff
$D$ is domain consistent with respect to $c$.

For domain $D$, checking \ibounds{}, \dbounds{}, or domain consistency
for $c$ are equivalent. Hence, the cases for checking  \ibounds{} 
and \dbounds{} consistency follow analogously.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Fuller Proof by Warwick to handle negative integers %%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ignore{%%Start Fuller Proof
SUBSET SUM: given A = {a_1 ,..., a_n}, find a subset sum to a_0

Here's a fuller proof that handles a_i of any sign.

First note that we can assume all a_i are non-zero (if a_i = 0 then it
doesn't change the value of the sum and thus is irrelevant for answering the
SUBSET SUM problem).  (Alternatively, the following still works fine even if
some a_i is 0.)

Let SP = sum of positive a_i.
Let SN = sum of negative a_i.

Second note that we may assume that a_0 > SN.  If a_0 < SN then the answer
to SUBSET SUM is trivially NO; if a_0 = SN then the answer to SUBSET SUM is
YES (select just the negative elements).

Domains are all {0, 1} as usual.
Constraint is  \Sum a_i x_i = SN + (SP - SN) x_-1 + (a_0 - SN) x_0

Then we have solutions:

x_0 = 0, x_-1 = 0, x_j = 0 (for positive a_j), x_j = 1 (for negative a_j)
x_0 = 0, x_-1 = 1, x_j = 1 (for positive a_j), x_j = 0 (for negative a_j)

(If a_j = 0 then we have support for both x_j = 0 and x_j = 1 if there is
any solution at all: toggling the value of x_j yields another solution.)

Thus we have guaranteed support for everything except x_0 = 1.  Thus D is
domain/bounds(D)/bounds(Z) consistent wrt the constraint iff x_0 = 1 is
domain/bounds(D)/bounds(Z) consistent wrt the constraint.

If x_0 = 1, x_-1 = 1 then the RHS is SP - SN + a_0, but since a_0 > SN this
is larger than SP, which is the largest the LHS can possibly be, so there
can be no such solution.

Thus the only way that x_0 = 1 can participate in a solution is if x_-1 = 0,
in which case the constraint reduces to  \Sum a_i x_i = a_0.  Thus x_0 = 1
is domain/bounds(D)/bounds(Z) consistent iff the answer to the corresponding
SUBSET SUM problem is YES.

Thus we have the following algorithm for polynomially reducing SUBSET SUM to
domain/bounds(D)/bounds(Z) consistency checking:

1)  Compute SN, SP.

2)  If a_0 < SN, answer NO.

3)  If a_0 = SN, answer YES.

4)  Otherwise, answer is equivalent to checking whether
	\Sum a_i x_i = SN + (SP - SN) x_-1 + (a_0 - SN) x_0
    with D(x_j) = {0,1} is domain/bounds(D)/bounds(Z) consistent.

Thus a polynomial consistency checker would allow us to solve SUBSET SUM in
polynomial time; thus the problem of checking consistency must be NP-hard.
}%%IGNORE End Fuller Proof

%\pjs{Killed example of subset sum no needed!}
\ignore{
\begin{example}
Consider an instance of the SUBSET SUM problem: 
given a set of integers $A = \{1, 2, 8\}$, 
determine if there is a set $S \subseteq A$ where the sum 
of the integers in $S$ is $3$.

Following the proof, we construct a 
linear equation $c \equiv 1(x_1) + 2(x_2) + 8(x_3) - 3(x_4) = 0$
with domain $D$ defined by $D(x_1) = D(x_2) = D(x_3) = \{0,1\}$
and $D(x_4) = \{1\}$.
We know $c$ is domain consistent with $D$ for $x_4$ since there exists
$\theta = \{ x_1 \mapsto 1, x_2 \mapsto 1, x_3 \mapsto 0, x_4 \mapsto 1\}$
which satisfies $c$ and $\theta(x_4) = 1$.
By collecting those $a_i$'s where $\theta(x_i) = 1$ for $1 \leq i \leq 3$,
we obtain a subset $\{1,2\}$ with the sum $3$.
\end{example}
}

There are constraints, however, for which \rbounds{} consistency
is less meaningful than other forms of consistency.

\begin{example}
Consider the global constraint 
$\calldiff(x_1,x_2,x_3) \equiv
x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$
and the domain $D_5$
where 
$D_5(x_1) = D_5(x_2) = \range{1}{2}$ and
$D_5(x_3) = \range{2}{3}$.
Then this domain is not \ibounds{} consistent, since
there is no integer solution with $x_3 = 2$. 
But the domain $D_5$ is \rbounds{} consistent
with $\calldiff(x_1,x_2,x_3)$
since it has real solutions
$\{ x_1 \mapsto 1, x_2 \mapsto 2, x_3 \mapsto 3\}$,
$\{ x_1 \mapsto 2, x_2 \mapsto 1, x_3 \mapsto 3\}$,
$\{ x_1 \mapsto 1, x_2 \mapsto 1.5, x_3 \mapsto 2\}$.
\end{example}

A problem with \rbounds{} consistency
is that it may not
be clear how to interpret an integer constraint in the reals.

\ignore{%% NOT true because of Gamma function
\begin{example}
Consider the constraint $x_1 = x_2!$ ($x_1$ is the factorial of $x_2$)
and the domain
$D_6(x_1) = D_6(x_2) = \range{0}{18}$,
then \ibounds{} consistency will demand the reduction
of domains to 
$D_7(x_1) = \range{1}{6}$, $D_7(x_2) = \range{0}{3}$.
Unfortunately to apply
\rbounds{} consistency 
we need to clarify what it means 
to be a real solution of $x_1 = x_2!$.%\pjs{Check \ibounds{} reasoning!}
\end{example}
}%%IGNORE
%\jeff{Revived the modulo example}
\begin{example}
Consider the constraint $x_1 = x_2 \mod x_3$.
\wh{Cut unimportant details of example}
\ignore{
The domain $D_6$ defined by
$D_6(x_1) = \range{1}{2}$, 
$D_6(x_2) = \range{0}{18}$, and
$D_6(x_3) = \range{0}{3}$
is not \ibounds{} consistent.
While the domain $D_7$ defined by
$D_7(x_1) = \range{1}{2}$, 
$D_7(x_2) = \range{1}{17}$, and
$D_7(x_3) = \range{2}{3}$
is \ibounds{} consistent,
supported by the integer solutions
$\{x_1 \mapsto 1, x_2 \mapsto 1, x_3 \mapsto 2\}$, and
$\{x_1 \mapsto 2, x_2 \mapsto 17, x_3 \mapsto 3\}$.
}
While this constraint is well-defined for integer values of the variables,
in order
to check \rbounds{} consistency 
we need to clarify what it means 
to be a \emph{real} solution of $x_1 = x_2 \mod x_3$.
%% NO MORE SPACE!
%In this case there is a reasonable real interpretation,
%e.g.\ $5.7 = 2.7 \mod 3$, but for the constraint
%$x_1 = 7 \mod x_2$, this becomes somewhat less obvious.
\end{example}

\wh{Added another example}
\jeff{reworded last sentence}
\begin{example}
Consider the reified constraint $b \Leftrightarrow x_1 + x_2 \leq x_3$,
where $b = 1$ corresponds to $x_1 + x_2 \leq x_3$ being true, and $b = 0$
corresponds to it being false.
%What sensible meaning can be assigned to $b = 0.5$?
However, it is not clear what natural interpretation can be given to, say,
$b = 0.5$.
\end{example}

\section{Conditions for Equivalence}\label{sec:equiv}

Why has the confusion between the various
definitions of bounds consistency not been noted before? 
In fact, for many constraints, the definitions are \emph{equivalent}.

\ignore{ %% Merge with n-ary monotonic constraints
\begin{lemma}\label{lemma:ineq}
Let $c \equiv \sum_{i=1}^n a_i x_i \leq a_0$.
Then \rbounds{} and \ibounds{} consistency for $c$ is equivalent.
\end{lemma}
\noproofs{
\begin{proof}
The \rbounds{} and domain propagators for
these constraints are identical (see Schulte \& Stuckey~\cite{SchulteStuckey-PPDP2001})
hence the result holds. 
\end{proof}
}%%NOPROOFS
} %%IGNORE

\ignore{%%Rephrased to fit our purpose
Zhang \& Yap~\cite{ZhangYap00} define $n$-ary monotonic constraints
as a generalization of linear inequalities $\sum_{i=1}^n a_i x_i \leq a_0$.
%An example of monotonic constraint is $x_1 \times x_2 \le x_3$.
For this class of constraints, \rbounds{}, \ibounds{} and \dbounds{}
consistency are equivalent to domain consistency. 

Given an $n$-ary constraint $c$ with 
$vars(c) = \{x_1, \ldots, x_n\}$
and total orderings  $\prec_i$ on $D_{init}(x_i),
1 \leq i \leq n$.
We say $c$ is is \emph{monotonic with respect to $x_i \in \vars(c)$ 
and orderings $\bar{\prec}$} 
(Zhang \& Yap~\cite{ZhangYap00})
if $\forall d \in D_{init}(x_i)$, $\forall d_j \in D_{init}(x_j)$, 
$\{x_1 \mapsto d_1, \ldots, x_{i-1} \mapsto d_{i-1}, x_i \mapsto d, x_{i+1} \mapsto d_{i+1}, \ldots, x_n \mapsto d_n\}$ 
is an integer solution of $c$ implies
$\{x_1 \mapsto d_1', \ldots, x_{i-1} \mapsto d_{i-1}', x_i \mapsto d', x_{i+1} \mapsto d_{i+1}', \ldots, x_n \mapsto d_n'\}$ is also an integer solution of $c$
for all $d' \prec_i d$ and $d_j \prec_j d_j'$ for $1 \le j \le n$, $j \ne i$.
}

\ignore{%% Use our new definition
Following the work of Zhang \& Yap~\cite{ZhangYap00} 
we define $n$-ary monotonic constraints\footnote{Our definition extends
the original definition~\cite{ZhangYap00} to real solutions
with the total ordering restricted to $(<)~\mbox{or}~(>)$ only.}
as a generalization of linear inequalities $\sum_{i=1}^n a_i x_i \leq a_0$.

\begin{defn}
An $n$-ary constraint $c$ is \emph{monotonic with respect to variable $x_i
\in vars(c)$} iff there exists a total ordering $\prec_k~ = (<)$ or 
$\prec_k~= (>)$ on $D(x_k)$ for $1 \leq k \leq n$ such that $\forall d$ and
$\forall d_j$, $\inf_D(x_i) \le d \le \sup_D(x_i)$, $\inf_D(x_j) \le d_j
\le \sup_D(x_j)$, $\{x_1 \mapsto d_1, \ldots, x_{i-1} \mapsto d_{i-1}, x_i
\mapsto d, x_{i+1} \mapsto d_{i+1}, \ldots, x_n \mapsto d_n\}$ is a real
solution of $c$ implies $\{x_1 \mapsto d_1', \ldots, x_{i-1} \mapsto
d_{i-1}', x_i \mapsto d', x_{i+1} \mapsto d_{i+1}', \ldots, x_n \mapsto
d_n'\}$ is also a real solution of $c$ for all $d' \prec_i d$ and $d_j
\prec_j d_j'$ for $1 \le j \le n$, $j \ne i$.  An $n$-ary constraint $c$ is
\emph{monotonic} iff $c$ is \emph{monotonic with respect to all variables in
$\vars(c)$.}
\end{defn}

Examples of monotonic constraints are: all linear inequalities, and 
$x_1 \times x_2 \le x_3$
with non-negative domain, e.g.\ $D(x_i) = \range{1}{1000}$
for $1 \le i \le 3$.
%An appropriate ordering on $D_k$ is $\prec_k = (<)$ for $1 \le k \le 3$.
For this class of constraints, \rbounds{}, \ibounds{} and \dbounds{}
consistency are equivalent to domain consistency. 

%\pjs{Check that it also implies domain consistency--it should--in fact
%we can almost say the result is a Corollary of Zhang and Yap,
%Check rewording of definition}
\begin{proposition}\label{lemma:monotone}
Let $c$ be an $n$-ary monotonic constraint.
%which is monotonic w.r.t.\ each variable $x_i$ and orderings $\prec_i$
%where $\prec_i = (<)$ or $\prec_i = (>)$, $1 \leq i \leq n$. 
%using the ordering $<$ or $>$.\footnote{Although 
%Zhang and Yap define $n$-ary monotonic constraints only in
%terms of integer solutions, but their definition can be extended 
%to real solutions straightforwardly.}
Then \rbounds{}, \ibounds{}, \dbounds{} and domain 
consistency for $c$ are all equivalent.
\end{proposition}
\noproofs{
\begin{proof}
Since domain consistency $\Rightarrow$ 
\dbounds{} consistency $\Rightarrow$ 
\ibounds{} consistency $\Rightarrow$
\rbounds{} consistency, 
it is sufficient to show here that \rbounds{} consistency 
implies domain consistency for this constraint; 
thus we assume $D$ is \rbounds{} consistent and prove it is also domain
consistent.

%First consider a bound of $x_i \in \vars(c)$, 
%say $d_i = \inf_D x_i$ (the other bound follows analogously).
%Since $D$ is \rbounds{} consistent, there exist reals
%$d_j, \inf_D x_j \leq d_j \leq \sup_D x_j, 1 \leq j \leq n, j \ne i$
%such that 
%$\{x_1 \mapsto d_1, \ldots, x_{i-1} \mapsto d_{i-1}, x_i \mapsto d, x_{i+1} \mapsto d_{i+1}, \ldots, x_n \mapsto d_n\}$ 
%is a real solution of $c$.
%By the definition of monotonic constraint, either
%$(d_j' = \lceil d_j \rceil) \ge d_j$ (natural ordering for $D(x_j)$) or
%$(d_j' = \lfloor d_j \rfloor) \le d_j$ (reverse ordering for $D(x_j)$)
%must form an integer solution of $c$. 
%These $d_j'$ exhibit that the bound $d_i$ is \ibounds{} consistent. 

First, consider a value $d \in D(x_i)$ where 
$x_i \in \vars(c)$, $d$ is the greatest value in the ordering of $D(x_i)$.
(i.e.\ it must be either $\inf_D x_i$ or $\sup_D x_i$, depending on
the ordering $\prec_i$ which makes $c$ monotonic w.r.t.\ $x_i$.)
Since $D$ is \rbounds{} consistent, there exist reals
$d_j, \inf_D x_j \leq d_j \leq \sup_D x_j, 1 \leq j \leq n, j \ne i$
such that  
$\{x_1 \mapsto d_1, \ldots, x_{i-1} \mapsto d_{i-1}, x_i \mapsto d, x_{i+1} \mapsto d_{i+1}, \ldots, x_n \mapsto d_n\}$ 
is a real solution of $c$.
By the definition of $n$-ary monotonic constraint, the value
$d_j \prec_j d_j'$ where $d_j'$ is the greatest value in the ordering
of $D(x_j)$
(i.e.\ $\inf_D x_j$ or $\sup_D x_j$ depends on the ordering $\prec_j$ which 
makes $c$ monotonic w.r.t.\ $x_i$) 
for all $1 \le j \le n, j \ne i$ must also form 
an integer solution of $c$, since $d_j' \in D(x_j)$ and must be integral.
Similarly, for all $d' \prec_i d$ and $d' \in D(x_i)$ can also form
an integer solution using the definition.
These exhibit that $D$ is also domain consistent.
\end{proof}
}%%NOPROOFS
}%%IGNORE

%\jeff{changed to our defn of monotonicity}
Following the work of Zhang \& Yap~\cite{ZhangYap00} 
we define $n$-ary monotonic constraints as a 
generalization of linear inequalities $\sum_{i=1}^n a_i x_i \leq a_0$.
Let $\theta \in_{\RR} D$ denote that $\theta(v) \in \RR$ and
$\inf_D v \leq \theta(v) \leq \sup_D v$ for all $v \in \vars(\theta)$.

\begin{defn}\label{defn:our-mon}
An $n$-ary constraint $c$ is \emph{monotonic with respect to variable
$x_i \in \vars(c)$} iff there exists a total ordering $\prec_i$ on
$D(x_i)$ such that if $\theta \in_{\RR} D$ is a real solution of $c$,
then so is any $\theta' \in_{\RR} D$ where $\theta'(x_j) = \theta(x_j)$ 
for $j \neq i$ and $\theta'(x_i) \preceq_i \theta(x_i)$.

An $n$-ary constraint $c$ is \emph{monotonic} iff $c$ 
is \emph{monotonic with respect to all variables in $\vars(c)$.}
\end{defn}

The above definition of
monotonic constraints is equivalent to but simpler than
that of Zhang \& Yap~\cite{ZhangYap00}; 
see Choi {\em et al.}~\cite{monotonicity} for justification and explanation.
\wh{Noted that we're only considering two possible total orders for
monotonicity.}
In the following, we assume that $\prec_i$ is $<$ or $>$ for all $i$, in
order to restrict ourselves to orders which are sensible with respect to
bounds consistency.

Examples of such monotonic constraints are:
\begin{itemize}
\item all linear inequalities
\item $x_1 \times x_2 \le x_3$
with non-negative domains, e.g.\ $D(x_i) = \range{1}{1000}$
for $1 \le i \le 3$.
\end{itemize}
For this class of constraints, \rbounds{}, \ibounds{} and \dbounds{}
consistency are equivalent to domain consistency. 

\begin{proposition}\label{lemma:monotone}
Let $c$ be an $n$-ary monotonic constraint.
Then \rbounds{}, \ibounds{}, \dbounds{} and domain 
consistency for $c$ are all equivalent.
\end{proposition}
\noproofs{
\begin{proof}
Since domain consistency $\Rightarrow$ 
\dbounds{} consistency $\Rightarrow$ 
\ibounds{} consistency $\Rightarrow$
\rbounds{} consistency, 
it is sufficient to show here that \rbounds{} consistency 
implies domain consistency for this constraint; 
thus we assume $D$ is \rbounds{} consistent and prove it is also domain
consistent.

\wh{Re-worked the proof}
Consider the greatest value $d_i \in D(x_i)$ for some $x_i \in \vars(c)$
(i.e.\ $d_i$ must be either $\inf_D x_i$ or $\sup_D x_i$ depending on the
ordering $\prec_i$ that makes $c$ monotonic w.r.t.\ $x_i$).
Since $D$ is \rbounds{} consistent, there exists $\theta \in_{\RR} D$ with
$\theta(x_i) = d_i$ such that $\theta$ is a real solution of $c$.

Let $\theta'(x_i) = \theta(x_i)$ and $\theta'(x_j) = d_j$ for all $j \neq i$
where $d_j$ is the smallest element of $D(x_j)$ with respect to $\prec_j$.
Since $c$ is monotonic, $\theta'$ is a solution of $c$, and since the
smallest elements of the domains are necessarily integers, $\theta'$ must be
an integer solution of $c$.

Now consider $\theta''$, where $\theta''(x_j) = \theta'(x_j)$ for all
$j \neq i$ and $\theta''(x_i) = d$ for some $d \in D(x_i)$.
Since $c$ is monotonic and $d \preceq_i \theta'(x_i)$ (since $\theta'(x_i)$
is the largest element of $D(x_i)$), $\theta''$ is also an integer solution
of $c$, with $\theta''(x_i) = d$.

Since the choice of $x_i$ and $d$ was arbitrary, we have shown that we can
construct an integer solution supporting any value in the domain of any
variable; thus $D$ is domain consistent.
\end{proof}
}%%NOPROOFS

Although disequality constraints are not monotonic, they are
equivalent for all the forms of bounds consistency because they
prune so weakly. 
%There are other constraints where \rbounds{}
%and \ibounds{} consistency is the same.

\begin{proposition}\label{lemma:disequal}
Let $c \equiv \sum_{i=1}^n a_i x_i \neq a_0$.
Then \rbounds{}, \ibounds{} and \dbounds{} consistency for $c$ are equivalent.
\end{proposition}
\noproofs{
\begin{proof}
(Sketch) Essentially if a value $d$ of a variable $x_i$ where $1 \le i \le n$ 
is supported by $c$, it is supported by an integer value in $D(x_i)$. 
Since either the domain of a variable is a singleton, 
in which case the bounds consistency must use the unique
integer, or the domain is not a singleton, and one
of the two integral endpoints will suffice. 
\end{proof}
}%%NOPROOFS

All forms of bounds consistency are also equivalent
for binary functional constraints, such as 
$a_1 x_1 + a_2 x_2 = a_0$, $x_1 = a {x_2}^2 \wedge x_2 \geq 0$,
or $x_1 = 1 + x_2 + {x_2}^2 + {x_2}^3 \wedge x_2 \geq 0$.
%% The previous two classes of constraint 
%% we examined above are those defined as endpoint-relevant

\begin{proposition}\label{lemma:bij}
Let $c$ be a constraint with $\vars(c) = \{x_1, x_2\}$,
where $c \equiv x_1 = g(x_2)$ and
$g$ is a bijective and monotonic function.
Then \rbounds{}, \ibounds{} and \dbounds{} consistency for $c$ are equivalent.
\end{proposition}
%% \begin{lemma}\label{lemma:bij}
%% Let $c$ be a constraint with $\vars(c) = \{x_1, x_2\}$
%% such that the relation $c$ is bijective and monotonic.
%% Then \rbounds{} and \ibounds{} consistency for $c$ are equivalent.
%% \end{lemma}
\noproofs{
\begin{proof}
Assume $D$ is \rbounds{} consistent w.r.t.\ $c$.
Let us examine the endpoints of the ranges of each variable.
We will examine $d_1 = \inf_D x_1$, 
and assume $g$ is monotonically increasing. The other cases are similar.

%Let $d_2 = f(d_1)$, then 
%$\{x_1 \mapsto d_1, x_2 \mapsto f(d_1)\}$ is the unique integer solution
%of $c$ supporting $d_1$. Hence $\inf_D x_2 \leq f(d_1) \leq \sup_D x_2$.
Now $\{x_1 \mapsto d_1, x_2 \mapsto g(d_1)\}$ is the unique
real solution of $c$ supporting $d_1$.
Hence $\inf_D x_2 \leq g(d_1) \leq \sup_D x_2$.
Suppose that $g(d_1) > \inf_D x_2 = d_2$. 
%Then $\inf_D x_1 = f^{-1}(f(d_1)) > f^{-1}(d_2)$, 
%hence $d_2$ cannot be supported by any integer value in the domain of $x_1$. 
Then $d_1 = g^{-1}(g(d_1)) > g^{-1}(d_2)$ since $g^{-1}$ is 
also monotonically
increasing.
Hence $d_2$ cannot be supported by any value in the domain of $x_1$.
Contradiction. Thus $d_2 = g(d_1) = \inf_D x_2$. 
Both $d_1 \in D(x_1)$ and $d_2 \in D(x_2)$ are integers 
since they are bounds.
Hence $\{x_1 \mapsto d_1, x_2 \mapsto g(d_1)\}$ is
an integer solution supporting $d_1$ for $x_1$.
Since the supporting solution only involves the end points 
in this case \ibounds{} and \dbounds{} are equivalent.
\end{proof}
}%%NOPROOFS

%% in~\cite{SchulteStuckey-PPDP2001}.
\noproofs{
The proofs 
%above that \rbounds{}, \ibounds{} 
%and \dbounds{} consistency are equivalent 
of Propositions~\ref{lemma:monotone},~\ref{lemma:disequal}, and~\ref{lemma:bij}
are related to but different from the proofs of
endpoint-relevance for these constraints 
in Schulte \& Stuckey~\cite{SchulteStuckey-PPDP2001}.

} %%NOPROOFS
\ignore{ %% special case of the next lemma
\begin{proposition}\label{lemma:range-preserv}
Let $c \equiv \sum_{i=1}^n a_i x_i = a_0$, 
where $|a_i| = 1$ for $1 \leq i \leq n$.
Then \rbounds{} and \ibounds{} consistency for $c$ is equivalent.
\end{proposition}
\noproofs{
\begin{proof}
Lemma 2.23 of Schulte \& Stuckey~\cite{SchulteStuckey-PPDP2001} show that
the \rbounds{} propagator $\bnd(c)$ is such that
$\bnd(c)(D) \bequiv \dom(c)(D)$ for any range
domain $D$, which ensures \ibounds{} consistency.
\end{proof}
}%%NOPROOFS
}%%IGNORE
%Finally we can show the result holds for linear equations with at
%most one non-unit coefficient.

For linear equations with at most one non-unit coefficient, 
we can show that \rbounds{} and \ibounds{} consistency are equivalent.

%% Thanks to Warwick
\begin{proposition}\label{lemma:range-preserv2}
Let $c \equiv \sum_{i=1}^n a_i x_i = a_0$,
where $|a_i| = 1, 2 \leq i \leq n$, $a_0$ and $a_1$ integral.
Then \rbounds{} and \ibounds{} consistency for $c$ are equivalent.
\end{proposition}
\noproofs{
\begin{proof}
\Ibounds{} consistency implies \rbounds{} consistency, so it is sufficient
to show here that \rbounds{} consistency implies \ibounds{} consistency for
this constraint; thus we assume $D$ is \rbounds{} consistent and prove it is
also \ibounds{} consistent.

First consider a bound of $x_1$, say $d_1 = \inf_D x_1$ (the other bound
follows analogously).
Since $D$ is \rbounds{} consistent, there exist real
$d_i, \inf_D x_i \leq d_i \leq \sup_D x_i, 2 \leq i \leq n$
such that $\{x_i \mapsto d_i ~|~ 1 \leq i \leq n\}$ is a real solution of $c$.
Note that $\sum_{i=2}^n a_i d_i$ is integral, and since $|a_i| = 1$
($2 \leq i \leq n$), it is straightforward to construct integral $d_i'$ with
the same sum that respect the variables' bounds.\footnote{
    For example, compute the average fractional part of the non-integral
    $d_i$s, and then round that fraction of them up to the next integer; the
    rest are rounded down.
    This clearly respects the variable bounds, because they are integral and
    we never change a value beyond an integer.
} %%FOOTNOTE
These $d_i'$ exhibit that the bound $d_1$ is \ibounds{} consistent.

Note that the fact that $x_1$ is \rbounds{} consistent also implies
\begin{equation}\label{eq:rbnd-impl}
\inf_D a_1 x_1 \geq a_0 - \sum_{i=2}^n \sup_D a_i x_i
\end{equation}

Now consider a bound of any of the other variables.
For simplicity we assume $a_2 = 1$ and consider the upper bound of $x_2$;
the other cases follow analogously.
Let $e_2 = \sup_D x_2$.
Since $D$ is \rbounds{} consistent, there exist real
$e_i, \inf_D x_i \leq e_i \leq \sup_D x_i, i \in \{1, 3 \ldots n\}$
such that $\{x_i \mapsto e_i ~|~ 1 \leq i \leq n\}$ is a real solution of $c$.
In particular, this means that
\[
\sup_D x_2 \leq a_0 - \inf_D a_1 x_1 - \sum_{i=3}^n \inf_D a_i x_i
\]
but~(\ref{eq:rbnd-impl}) implies
\[
\sup_D x_2 \geq a_0 - \inf_D a_1 x_1 - \sum_{i=3}^n \sup_D a_i x_i
\]
This means $\sup_D x_2 = a_0 - \inf_D a_1 x_1 - k$ where $k$ is an integer
and
$\sum_{i=3}^n \inf_D a_i x_i \leq k \leq \sum_{i=3}^n \sup_D a_i x_i$.
Clearly we can find integer values $f_i$ to assign to $x_i$
($3 \leq i \leq n$) to make their sum equal to $k$ while satisfying the
variable bounds, since the corresponding $a_i$ are $\pm 1$.
If we let $f_2 = \sup_D x_2$ and let $f_1$ be such that
$a_1 f_1 = \inf_D a_1 x_1$, then
$\{x_i \mapsto f_i, 1 \leq i \leq n\}$ is an integer solution of $c$ that
exhibits that $\sup_D x_2$ is \ibounds{} consistent.
\end{proof}
}%%NOPROOFS

\ignore{%% implicit from the NP-harness argument
Interestingly \rbounds{} consistency 
and \ibounds{} consistency are not even identical 
when the variables involved all have domains $\range{0}{1}$.

\begin{example}
The constraint $2x_1 = (x_2 + x_3)^2$ where
$D(x_1) = D(x_2) = D(x_3) = \range{0}{1}$
is \rbounds{} consistent. Real solutions illustrating this are
$\{x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 0\}$,
$\{x_1 \mapsto 1, x_2 \mapsto 1, x_3 \mapsto \sqrt{2}-1\}$,
$\{x_1 \mapsto 1, x_2 \mapsto \sqrt{2}-1, x_3 \mapsto 1\}$.
It is not \ibounds{} consistent, 
since the unique integer solution is 
$\{x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 0\}$.
\end{example}

%% More Examples from Warwick
\begin{example}\label{example:linear01}
The constraint $3 x_1 + 5 x_2 + 7 x_3 = 7$
where $D(x_1) = D(x_2) = D(x_3) = \range{0}{1}$
is \rbounds{} consistent.
Real solutions illustrating this are
$\{x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 0\}$,
$\{x_1 \mapsto 1, x_2 \mapsto 0.8, x_3 \mapsto 0\}$,
$\{x_1 \mapsto \frac{2}{3}, x_2 \mapsto 1, x_3 \mapsto 0\}$.
It is not \ibounds{} consistent, since the unique integer solution is
$\{x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 0\}$.
\end{example}

%% And an even simpler constraint
\begin{example}\label{example:linear02}
The constraint $x_1 + 2 x_2 + 2 x_3 = 2$
where $D(x_1) = D(x_2) = D(x_3) = \range{0}{1}$
is \rbounds{} consistent.
Real solutions illustrating this are
$\{x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 1\}$,
$\{x_1 \mapsto 0, x_2 \mapsto 1, x_3 \mapsto 0\}$,
$\{x_1 \mapsto 1, x_2 \mapsto \frac{1}{2}, x_3 \mapsto 0\}$.
It is not \ibounds{} consistent, since there is clearly no integer solution
with $x_1 \mapsto 1$.
\end{example}
} %%IGNORE


Even for linear equations with all unit coefficients,
\dbounds{} consistency is different from \ibounds{} and \rbounds{}
consistency.

\begin{example}[Counter example]
Consider the linear equation  $c \equiv x_1 + x_2 + x_3 = 5$ and the 
domain $D_8$ where 
$D_8(x_1) = \range{0}{3}$, $D_8(x_2) = D_8(x_3) = \{0,3,4,5\}$.
$D_8$ is \rbounds{} and \ibounds{} consistent as given by 
the following solutions of $c$:
$\{ x_1 \mapsto 0, x_2 \mapsto 0, x_3 \mapsto 5 \}$,
$\{ x_1 \mapsto 0, x_2 \mapsto 5, x_3 \mapsto 0 \}$, and
$\{ x_1 \mapsto 3, x_2 \mapsto 1, x_3 \mapsto 1 \}$.
$D_8$ is, however, not \dbounds{} consistent, 
since there is clearly no integer solution with $x_1 \mapsto 3$
(i.e.\ neither $1$ nor $2$ are in the domains of $x_2$ and $x_3$).
\end{example}

In summary for many of the constraints commonly used the notions
of bounds consistency are equivalent, but clearly not for all.

\section{Related Work}\label{sec:related}

In this paper we restricted ourselves to \emph{integer} constraint solving. 
Definitions of bounds consistency for \emph{real} constraints 
are also numerous, but their similarities and differences
have been noted and explained by  
e.g. Benhamou \bgroup \em et al.\egroup~\cite{newton}.
Indeed, we can always interpret integers as reals
and apply bounds consistency for real constraints plus 
appropriate rounding, e.g.\ CLP(BNR)~\cite{clpbnr}.
However, as we have pointed out in Section~\ref{sec:bc}, 
there exist integer constraints for which propagation is
less meaningful when interpreted as reals.

\jeff{reworded}
\ignore{
Lhomme~\cite{Lhomme93} defines \emph{arc B-consistency} which 
formalizes bounds propagation for both integer and real constraints.
He proposes an efficient propagation algorithm implementing
arc B-consistency with complexity analysis and experimental results. 
However, his study focuses on constraints defined 
by numeric relations (i.e.\ numeric CSPs).
%In practice, we do bounds propagation also globally, e.g.\ alldiff
}%% IGNORE
Lhomme~\cite{Lhomme93} defines \emph{arc B-consistency} which 
formalizes bounds propagation techniques for numeric CSPs.
Unlike our definition of CSPs, constraints in numeric CSPs 
cannot be given extensionally and must be defined by numeric relations, 
which can be interpreted in either the real or the finite integer domain.
Numeric CSPs also restrict the domain of variables to be a single interval.

Walsh~\cite{toby-rc} introduces several new forms of bounds consistency
which extends the notion of $(i,j)$-consistency 
and relational consistency.
He gives a theoretical analysis comparing the propagation strength
of these new forms of bounds consistency.
%% but not sure when are they practical in practice

Maher~\cite{prop-comp} introduces the notion of propagation completeness
together with a general framework to unify a wide range of 
consistency. 
These include hull consistency of real constraints
and \ibounds{} consistency of integer constraints.
Propagation completeness aims to capture the timeliness 
property of propagation.
%% while our is to compare their propagation strength

The application of bounds consistency is not limited to integer
and real constraints. 
Bounds consistency has been formalized for solving 
set constraints~\cite{conjunto}, and more recently, 
multiset constraints~\cite{multiset-cp03}.

\section{Conclusion}\label{sec:concl}

The contributions of this paper are two-fold.
First, we point out that the three commonly used definitions 
of bounds consistency are incompatible.
Second, we clarify their differences and show that for 
several types of constraints, \rbounds{}, \ibounds{} 
and \dbounds{} consistency are equivalent.
This explains partly why the discrepancies among the definitions
were not noticed earlier.
Our precise definitions can serve as the basis for 
verifying all implementations of bounds propagators.

%\jeff{drop future work}
\ignore{%%IGNORE
An important direction for future work is 
to build efficient \rbounds{} and/or \ibounds{} propagators 
for new classes of constraints.
\Dbounds{} consistency resembles much of domain consistency,
%and appears significantly more complicated to
%compute than \ibounds{} or \rbounds{} consistency, 
yet only makes guarantees about the endpoints of the domain.
It would be interesting to determine whether there are some CSPs
where \dbounds{} propagators would be advantageous.
}%%IGNORE

\bibliographystyle{abbrv}
\bibliography{paper}

\end{document}

technotes.bbl
\begin{thebibliography}{10}

\bibitem{apt-book}
K.~Apt.
\newblock {\em Principles of Constraint Programming}.
\newblock Cambridge University Press, 2003.

\bibitem{newton}
F.~Benhamou, D.~{McAllester}, and P.~{Van Hentenryck}.
\newblock {CLP(Intervals)} revisited.
\newblock In {\em ILPS 1994}, pages 124--138, 1994.

\bibitem{clpbnr}
F.~Benhamou and W.~J. Older.
\newblock Applying interval arithmetic to real, integer, and boolean
  constraints.
\newblock {\em JLP}, 32(1):1--24, 1997.

\bibitem{eclipse-intro}
A.~M. Cheadle, W.~Harvey, A.~J. Sadler, J.~Schimpf, K.~Shen, and M.~G. Wallace.
\newblock {\eclipse}: An introduction.
\newblock Technical Report IC-Parc-03-1, {IC-Parc}, Imperial College London,
  2003.

\bibitem{monotonicity}
C.~W. Choi, W.~Harvey, J.~H.~M. Lee, and P.~J. Stuckey.
\newblock A note on the definition of constraint monotonicity.
\newblock Available from
  \url{http://www.cse.cuhk.edu.hk/~cwchoi/monotonicity.pdf}, 2004.

\bibitem{clr}
T.~H. Cormen, C.~E. Leiserson, and R.~L. Rivest.
\newblock {\em Introduction to Algorithms}.
\newblock The MIT Press, 1990.

\bibitem{rina-book}
R.~Dechter.
\newblock {\em Constraint Processing}.
\newblock Morgan Kaufmann, 2003.

\bibitem{toby-cp02}
A.~Frisch, B.~Hnich, Z.~Kiziltan, I.~Miguel, and T.~Walsh.
\newblock Global constraints for lexicographic orderings.
\newblock In {\em CP2002}, pages 93--108. Springer-Verlag, 2002.

\bibitem{conjunto}
C.~Gervet.
\newblock Interval propagation to reason about sets: Definition and
  implementation of a practical language.
\newblock {\em Constraints}, 1(3):191--244, 1997.

\bibitem{warwick-joachim}
W.~Harvey and J.~Schimpf.
\newblock Bounds consistency techniques for long linear constraints.
\newblock In {\em Proceedings of TRICS: Techniques foR Implementing Constraint
  programming Systems}, pages 39--46, 2002.

\bibitem{solver52}
{ILOG Solver}.
\newblock {\em {ILOG Solver} 5.2: User's Manual}, 2001.

\bibitem{arnaud}
A.~Lallouet, A.~Legtchenko, T.~Dao, and A.~Ed-Dbali.
\newblock Intermediate (learned) consistencies.
\newblock Research Report RR-LIFO-2003-04, Laboratoire d'Informatique
  Fondamentale d'Orl{\'e}ans, 2003.

\bibitem{Lhomme93}
O.~Lhomme.
\newblock Consistency techniques for numeric {CSPs}.
\newblock In {\em IJCAI-93}, pages 232--238, 1993.

\bibitem{mackworth}
A.~K. Mackworth.
\newblock Consistency in networks of relations.
\newblock {\em AI Journal}, 8(1):99--118, 1977.

\bibitem{prop-comp}
M.~Maher.
\newblock Propagation completeness of reactive constraints.
\newblock In {\em ICLP 2002}, pages 148--162, 2002.

\bibitem{book}
K.~Marriott and P.~J. Stuckey.
\newblock {\em Programming with Constraints: an Introduction}.
\newblock The MIT Press, 1998.

\bibitem{gac4}
R.~Mohr and G.~Masini.
\newblock Good old discrete relaxation.
\newblock In {\em ECAI-88}, pages 651--656, 1998.

\bibitem{puget-alldifferent}
J.-F. Puget.
\newblock A fast algorithm for the bound consistency of alldiff constraints.
\newblock In {\em AAAI-98}, pages 359--366, 1998.

\bibitem{vanBeek-gcc}
C.-G. Quimper, P.~{van Beek}, A.~L{\'o}pez-Ortiz, A.~Golynski, and S.~B.
  Sadjad.
\newblock An efficient bounds consistency algorithm for the global cardinality
  constraint.
\newblock In {\em CP 2003}, pages 600--614, 2003.

\bibitem{sum-diff}
J.-C. R{\'e}gin and M.~Rueher.
\newblock A global constraint combining a sum constraint and difference
  constraints.
\newblock In {\em CP 2000}, pages 384--395, 2000.

\bibitem{SchulteStuckey-PPDP2001}
C.~Schulte and P.~J. Stuckey.
\newblock When do bounds and domain propagation lead to the same search space.
\newblock In {\em PPDP 2001}, pages 115--126, 2001.

\bibitem{sics}
{SICStus Prolog}.
\newblock {\em {SICStus Prolog User's Manual, Release 3.10.1}}, 2003.

\bibitem{pdv2}
P.~{Van Hentenryck}, V.~Saraswat, and Y.~Deville.
\newblock Design, implementation and evaluation of the constraint language
  cc({FD}).
\newblock {\em JLP}, 37(1--3):139--164, 1998.

\bibitem{toby-rc}
T.~Walsh.
\newblock Relational consistencies.
\newblock Research Report APES-28-2001, APES Research Group, 2001.

\bibitem{multiset-cp03}
T.~Walsh.
\newblock Consistency and propagation with multiset constraints: A formal
  viewpoint.
\newblock In {\em CP 2003}, 2003.
\newblock 724--738.

\bibitem{ZhangYap00}
Y.~Zhang and R.~H.~C. Yap.
\newblock Arc consistency on $n$-ary monotonic and linear constraints.
\newblock In {\em CP 2000}, pages 470--483, 2000.

\end{thebibliography}
