% Paper on binary submodular constraints
% Cohen, Cooper, Jeavons, Krokhin - summer work 2002
% This version started by MC, October 2002
% Turned into LateX, thoroughly revised proofs, and shortened, DC, November 2002
% Prepared for IJCAI, PJ, December 2002
% Revised with more examples, omitting main proof, by PJ, January 2003
% Journal version begun May 20, 2003, by PJ
% Revised June 6, 2003, by PJ to incorporate (small) comments of MC and AK
% Revised June 17, 2003, by PJ to incorporate comments of DAC
% Revised December 1 2003 for JAIR
% Reformatted and minor revisions in response to JAIR referees, February 2004
% Final revisions (avoiding citations as nouns!) after acceptance notification, March 5, 2004
% Minor tweaks to formatting suggested by Steve Minton, May 14, 2004

\documentstyle[jair,11pt,theapa,epsfig,amssymb]{article}
% \usepackage{ijcai03}
% \bibliographystyle{named}
% \usepackage{theapa}
% \bibliographystyle{plain}
\bibliographystyle{theapa}

\jairheading{22}{2004}{1-22}{12/03}{7/04}
\firstpageno{1}

\ShortHeadings{A Maximal Tractable Class of Soft Constraints}
{Cohen, Cooper, Jeavons, \& Krokhin}

% \usepackage{times}
% \usepackage{amsmath}
% \usepackage{epsfig}
% \usepackage{amssymb}
% \usepackage{latexsym}
% \usepackage{amsfonts}
% \usepackage{color}
% \usepackage{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some useful abbreviations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ensuremath}[1]{\mbox{$#1$}} % Required in Latex 2.09
\newcommand{\operatorname}[1]{\mbox{\rm #1}} % Required in Latex 2.09
\newcommand{\text}[1]{\mbox{#1}}         % Required in Latex 2.09

\newcommand{\infinity}{\ensuremath{\infty}}
\newcommand{\csp}{constraint satisfaction problem\ }
\renewcommand{\P}{\ensuremath{\cal P}}
\newcommand{\C}{\ensuremath{\cal C}}
\newcommand{\tuple}[1]{\ensuremath{\langle #1 \rangle}}
\newcommand{\GIF}[3]{\ensuremath{\eta_{[{#2},{#3}]}^{#1}}}
\newcommand{\sCSP}[1]{\ensuremath{\operatorname{sCSP}(#1)}}
\newcommand{\MF}[1]{\ensuremath{G_{#1}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

% {\theorembodyfont{\upshape}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{exmp}[theorem]{Example}
\newtheorem{construction}[theorem]{Construction}
% }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Comments, Omissions, Proofs, and Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{\small {\em[*** {#1} ***]}\normalsize }
\newcommand{\omitted}[1]{}
% \newcommand{\omitted}[1]{#1}
\newenvironment{proof}{\noindent {\bf Proof:\ }}{\hspace*{\fill} \qed\\}
\def\qed{\hbox{${\vcenter{\vbox{
        \hrule height 0.4pt\hbox{\vrule width 0.4pt height 6pt
        \kern5pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}} % nice rt margin symbol
\newenvironment{example}{\begin{exmp} \rm  }{\hspace*{\fill} \qed \end{exmp}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Helpful Maths commands := and Restrict
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\defequals}{\ensuremath{\stackrel{\mathrm{def}}{=}}}
\newcommand{\restrict}[2]{\ensuremath{{#1}_{\mid_{#2}}}} % Restrict fns to
                                                         % some pattern

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Debugging for labels
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\mylabel}[1]{\label{#1} \footnotesize {\bf [{#1}]}\normalsize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Control of LaTeX reporting
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small

\begin{document}
\title{A Maximal Tractable Class of Soft Constraints}

\author{\name David Cohen \email d.cohen@rhul.ac.uk\\
\addr Computer Science Department\\
Royal Holloway, University of London, UK
\AND
\name Martin Cooper \email cooper@irit.fr\\
\addr IRIT\\
University of Toulouse III, France
\AND
\name Peter Jeavons \email peter.jeavons@comlab.ox.ac.uk\\
\addr OUCL\\
University of Oxford, UK
\AND
\name Andrei Krokhin \email ak@dcs.warwick.ac.uk \\
\addr Computer Science Department\\
University of Warwick, UK
}

\maketitle

\begin{abstract}
Many researchers in artificial intelligence are beginning to explore the
use of soft constraints to express a set of (possibly conflicting) problem requirements.
A soft constraint is a function defined on a collection of variables
which associates some measure of desirability
with each possible combination of values for those variables.
However, the crucial question of the computational complexity of finding the optimal solution
to a collection of soft constraints has so far received very little attention.
In this paper we identify a class of soft binary constraints
for which the problem of finding the optimal solution is tractable.
In other words, we show that for any given set of such constraints,
there exists a polynomial time algorithm to determine the assignment having the best
overall combined measure of desirability.
This tractable class includes many commonly-occurring soft
constraints, such as ``as near as possible" or ``as soon as possible after",
as well as crisp constraints such as ``greater than".
Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft
binary constraint which is not in the class gives rise to a class of problems which is NP-hard.
\end{abstract}

\omitted{
\textbf{Keywords: }NP-hardness, submodular functions, valued
constraints, tractable constraint class, maximum flow problem.
}

\section{Introduction}

The constraint satisfaction framework is
widely acknowledged as a convenient and efficient way to model and solve a wide variety
of problems arising in Artificial Intelligence,
including planning~\shortcite{Kautz92:planning}
and scheduling~\shortcite{vanBeek92:temporal},
image processing~\shortcite{Montanari74:constraints}
and  natural language understanding~\shortcite{Allen94:natural}.

In the standard framework a {\em constraint} is usually taken to be a predicate, or relation,
specifying the allowed combinations of values for some fixed collection of variables:
we will refer to such constraints here as {\em crisp} constraints.
A number of authors have suggested that the usefulness of the constraint satisfaction
framework could be greatly enhanced by extending the definition of a constraint
to include also {\em soft} constraints, which allow different measures of desirability
to be associated with different combinations of values~\shortcite{Bistarelli97:semiring,Bistarelli99:semiringVCSP}.
In this extended framework a constraint can be seen as a {\em function}, mapping
each possible combination of values to a measure of desirability or undesirability.
Finding a solution to a set of constraints then means finding an assignment of values to
all of the variables which has the best overall combined desirability measure.
%
\begin{example}
\label{ex:optim}
Consider an optimization problem with $2n$ variables, $v_1, v_2, \ldots, v_{2n}$,
where we wish to assign each
variable an integer value in the range $1,2,\ldots,n$, subject to the following restrictions:
\begin{itemize}
\item Each variable $v_i$ should be assigned a value that is as close as possible to $i/2$.
\item Each pair of variables $v_i$, $v_{2i}$ should be assigned a pair of values that are
as close as possible to each other.
\end{itemize}
To model this situation we might impose the following soft constraints:
\begin{itemize}
\item A unary constraint on each $v_i$ specified by a function $\psi_i$, \\
where $\psi_i(x) = (x - i/2)^2$.
\item A binary constraint on each pair $v_i,v_{2i}$ specified by a function $\delta_r$, \\
where $\delta_r(x,y) = |x-y|^r$ for some $r \ge 1$.
\end{itemize}
We would then seek an assignment to all of the variables which minimizes
the sum of all of these constraint functions,
\[
\sum_{i=1}^{2n} \psi_i(v_i) + \sum_{i=1}^{n} \delta_r(v_i,v_{2i}).
\]
\end{example}
%
The cost of allowing additional flexibility in the specification of
constraints, in order to model requirements of this kind,
is generally an increase in computational difficulty.
In the case of
crisp constraints there has been considerable progress in identifying classes
of constraints which are {\em tractable}, in the sense that there exists a polynomial time
algorithm to determine whether or not any collection of constraints from such a class
can be simultaneously satisfied~\shortcite{Bulatov03:conservative,Feder98:monotone,Jeavons97:closure}.
In the case of soft constraints there has been a detailed investigation of the tractable cases for
Boolean problems (where each variable has just 2 possible values)~\shortcite{Creignouetal:siam01},
but very little investigation of the tractable cases over larger finite domains,
even though there are many significant results in the literature
on combinatorial optimization which are clearly relevant to this
question~\shortcite{Nemhauser88:optimization}.

The only previous work
we have been able to find on the complexity of non-Boolean soft constraints
is a paper by~\shortciteA{Khatib01:temporal}, which describes a family of tractable soft temporal constraints.
However, the framework for soft constraints used by~\shortciteA{Khatib01:temporal} is different
from the one we use here, and the results are not directly comparable.
We discuss the relationship between this earlier work and ours more fully in Section~\ref{sec-applications}.

In this paper we make use of the idea of a
{\em submodular function}~\shortcite{Nemhauser88:optimization}
to identify a general class of soft constraints for which there exists
a polynomial time solution algorithm.
Submodular functions are widely used in economics and
operational research~\shortcite{Fujishige91:submodular,Nemhauser88:optimization,Topkis98:supermodular},
and the notion of submodularity provides a kind of discrete analogue of convexity~\shortcite{Lovasz83:submodular}.

Submodular functions are usually defined~\shortcite{Nemhauser88:optimization} as real-valued functions on
sets (which may be viewed as Boolean tuples), but we consider
here the more general case of functions on tuples over an arbitrary finite domain (as in~\shortciteR{Topkis78:submodular}).
We also allow our functions to take infinite values.
By establishing a new decomposition result for binary submodular functions of this kind,
% (Theorem~\ref{mainDecomp}),
we obtain a cubic time algorithm
to find the optimal assignment for any set of soft constraints which can be defined using them
(such as the constraints in Example~\ref{ex:optim}).
Because our algorithm is specially devised for submodular functions that are expressed as a combination of binary
functions,
it is much more efficient in this case than existing general algorithms for
submodular function minimization~\shortcite{Schrijver00:submodular,Iwata01:submodular}.

We give a number of examples to illustrate the many different forms of soft
constraint that can be defined using binary submodular functions, and we also show that
this class is {\em maximal}, in the sense that no other form of binary constraint can be added
to the class without sacrificing tractability.

\section{Definitions}

To identify a tractable class of soft constraints we will need to restrict the set
of functions that are used to specify constraints. Such a restricted set of possible functions
will be called a soft constraint {\em language}.
%
\begin{definition}
Let $D$ and $E$ be fixed sets.
A {\em soft constraint language over $D$ with evaluations in $E$} is defined to be
a set of functions, $\Gamma$, such that each $\phi \in \Gamma$
is a function from $D^k$ to $E$, for some $k \in \mathbb{N}$, where $k$ is called the arity of $\phi$.
\end{definition}
%
For any given choice of soft constraint language, $\Gamma$, we define an associated
soft constraint satisfaction problem, which we will call $\sCSP{\Gamma}$, as follows.
%
\begin{definition}
Let $\Gamma$ be a soft constraint language over $D$ with evaluations in $E$.
An instance $\P$ of $\sCSP{\Gamma}$ is a triple $\tuple{V,D,C}$,
where:
\begin{itemize}
\item $V$ is a finite set of {\em variables}, which must be assigned values from the set $D$.
\item $C$ is a set of {\em soft constraints}.
Each $c \in C$ is a pair $\tuple{\sigma, \phi}$ where:
% \begin{itemize}
% \item
$\sigma$ is a list of variables, of length $|\sigma|$, called the {\em scope} of $c$; and
% \item
$\phi$ is an element of $\Gamma$ of arity $|\sigma|$,
called the {\em evaluation function} of\ \ $c$.
% \end{itemize}
\end{itemize}
\end{definition}
%
% Note that, for any constraint $c = \tuple{\sigma,\phi}$, the arity of the
% constraint is given by $|\sigma|$, the length of the constraint scope.
The evaluation function $\phi$ will be used to specify some measure of desirability or
undesirability associated with each possible tuple of values over $\sigma$.

To complete the definition of a soft constraint satisfaction problem we need
to define how the evaluations obtained from each evaluation function
are combined and compared, in order to define what
constitutes an optimal overall solution.
Several alternative mathematical approaches to this issue
have been suggested in the literature:
\begin{itemize}
\item
In the semiring based approach~\shortcite{Bistarelli97:semiring,Bistarelli99:semiringVCSP}, the set of possible evaluations, $E$,
is assumed to be an algebraic structure equipped with two binary operations, satisfying the axioms of
a semiring.
One example of such a structure is the real interval $[0,1]$, equipped with the
operations $\min$ and $\max$, which corresponds to the conjunctive
fuzzy CSP framework~\shortcite{Rosenfeld76:relaxation,Ruttkay94:fuzzy}.
Another example is the set $\{0,1,2,\ldots\} \cup \{\infinity\}$,
equipped with the operations {\em max} and {\em plus},
which corresponds to the weighted CSP framework~\shortcite{Bistarelli99:semiringVCSP}.

\item
In the valued CSP approach~\shortcite{Bistarelli99:semiringVCSP}, the set of possible evaluations $E$ is assumed
to be a totally ordered algebraic structure with a top and bottom element and
a single monotonic binary operation known as {\em aggregation}.
One example of such a structure is
the set of multisets over some finite ordered set together with a top element, equipped
with the operation of multiset union, which corresponds to the lexicographic CSP
framework~\shortcite{Bistarelli99:semiringVCSP}.
\end{itemize}
%
For our purposes, we require the same properties as the valued CSP
approach, with the additional requirement that
the aggregation operation has a partial inverse,
such that evaluations other than the top element may be ``cancelled'' when occurring on both sides of an inequality.
For simplicity, we shall assume throughout this paper that
the set of evaluations $E$ is either the set
of non-negative integers together with infinity, or else the set of non-negative
real numbers together with infinity\footnote{Many of our results can be extended to more general evaluation structures,
such as the {\em strictly monotonic} structures described by~\citeA{Cooper03:reduction}, but
we will not pursue this idea here.}.
Hence, throughout this paper the bottom element in the evaluation structure is $0$, the top element is $\infinity$,
and for any two evaluations $\rho_1,\rho_2 \in E$,
the aggregation of $\rho_1$ and $\rho_2$ is given by $\rho_1 + \rho_2 \in E$.
Moreover, when $\rho_1 \ge \rho_2$ we also have
$\rho_1 - \rho_2 \in E$.
(Note that we set $\infinity - \infinity = \infinity$).


The elements of the set $E$ are used to represent different measure of undesirability,
or {\em penalties},
associated with different combinations of values.
This allows us to complete the definition of a soft constraint satisfaction problem
with the following simple definition of a solution to an instance.
%
\begin{definition}
For any soft constraint satisfaction problem instance $\P = \tuple{V,D,C}$,
an {\em assignment} for $\P$ is a mapping $t$ from $V$ to $D$. The {\em evaluation} of
an assignment\ \ $t$, denoted $\Phi_{\P}(t)$, is given by the sum (i.e., aggregation)
of the evaluations for the restrictions of
$t$ onto each constraint scope, that is,
\[
\Phi_{\P}(t) = \sum_{\tuple{\tuple{v_1,v_2,\ldots,v_k},\phi} \in C} \phi(t(v_1),t(v_2),\ldots,t(v_k)).
\]
A {\em solution} to $\P$ is an assignment with the smallest possible evaluation,
and the question is to find a solution.
\end{definition}
%
\begin{example}
\label{ex-crisp}
For any standard constraint satisfaction problem instance $\P$ with crisp constraints,
we can define a corresponding soft constraint satisfaction problem instance $\widehat{\P}$
in which the range of the evaluation functions of all the constraints is the set $\{0,\infty\}$.
For each crisp constraint $c$ of $\P$, we define a corresponding soft constraint $\widehat{c}$ of $\widehat{\P}$ with the same scope;
the evaluation function of $\widehat{c}$ maps each tuple allowed by $c$ to 0, and each tuple disallowed by $c$ to $\infty$.

In this case the evaluation of an assignment $t$ for $\widehat{\P}$ equals the minimal possible evaluation, 0,
if and only if $t$ satisfies all of the crisp constraints in $\P$.
\end{example}
%
\begin{example}
\label{ex-maxCSP}
For any standard constraint satisfaction problem instance $\P$ with crisp constraints,
we can define a corresponding soft constraint satisfaction problem instance $\P^\#$
in which the range of the evaluation functions of all the constraints is the set $\{0,1\}$.
For each crisp constraint $c$ of $\P$, we define a corresponding soft constraint $c^\#$ of $\P^\#$ with the same scope;
the evaluation function of $c^\#$ maps each tuple allowed by $c$ to 0, and each tuple disallowed by $c$ to $1$.

In this case the evaluation of an assignment $t$ for $\P^\#$
equals the number of crisp constraints in $\P$ which are violated by $t$.
Hence a solution to $\P^\#$ corresponds to an assignment which
violates the minimal number of constraints of $\P$, and hence satisfies the maximal number of constraints of $\P$.
Finding assignments of this kind is generally referred to as solving the
{\sc Max-CSP} problem~\shortcite{Freuder92:partial,Larrosa99:reversible}.
\end{example}
%
Note that the problem of finding a solution to a soft constraint satisfaction problem
is an NP optimization problem, that is, it lies in the complexity class NPO
(see~\shortciteR{Creignouetal:siam01} for a formal definition of this class).
If there exists a polynomial-time algorithm which finds a solution to all
instances of $\sCSP{\Gamma}$, then we shall say that $\sCSP{\Gamma}$ is {\em tractable}.
On the other hand, if there is a polynomial-time reduction from some
NP-complete problem to $\sCSP{\Gamma}$, then
we shall say that $\sCSP{\Gamma}$ is {\em NP-hard}.
%
\begin{example}
\label{ex-Boolean}
Let $\Gamma$ be a soft constraint language over $D$, where $|D| = 2$.
In this case $\sCSP{\Gamma}$ is a class of
{\em Boolean} soft constraint satisfaction problems.

If we restrict $\Gamma$ even further, by only allowing functions with range $\{0,\infinity\}$,
as in Example~\ref{ex-crisp},
then $\sCSP{\Gamma}$ corresponds precisely to a standard
Boolean {\em crisp} constraint satisfaction problem. Such problems are sometimes
known as {\sc Generalized Satisfiability} problems~\shortcite{Schaefer78:complexity}.
The complexity of $\sCSP{\Gamma}$ for such restricted sets $\Gamma$ has been
completely characterised, and it has been shown that there are precisely six tractable
cases~\shortcite{Schaefer78:complexity,Creignouetal:siam01}.

Alternatively,
if we restrict $\Gamma$ by only allowing functions with range $\{0,1\}$,
as in Example~\ref{ex-maxCSP},
then $\sCSP{\Gamma}$ corresponds precisely to a standard
Boolean {\em maximum satisfiability} problem, in which the aim is to satisfy the maximum
number of crisp constraints. Such problems are sometimes
known as {\sc Max-Sat} problems~\shortcite{Creignouetal:siam01}.
The complexity of $\sCSP{\Gamma}$ for such restricted sets $\Gamma$ has been
completely characterised, and it has been shown that there are precisely three tractable cases
(see Theorem~7.6 of~\shortciteR{Creignouetal:siam01}).

We note, in particular, that when $\Gamma$ contains just the single binary function $\phi_{XOR}$
defined by
\[
\phi_{XOR}(x,y) = \left\{\begin{array}{ll}
0\ & \text{if}\ x \neq y\\
1  & \text{otherwise}
\end{array}\right.
\]
then $\sCSP{\Gamma}$ corresponds to the {\sc Max-Sat} problem for the exclusive-or
predicate, which is known to be NP-hard (see Lemma~7.4 of ~\shortciteR{Creignouetal:siam01}).
\end{example}
%
\begin{example}
\label{ex-ternary}
Let $\Gamma$ be a soft constraint language over $D = \{1,2,\ldots,M\}$, where $M  \ge 3$,
and assume that $\Gamma$ contains just the set of all unary functions, together with the single binary
function $\phi_{EQ}$ defined by
\[
\phi_{EQ}(x,y) = \left\{\begin{array}{ll}
0\ & \text{if}\ x = y\\
1  & \text{otherwise.}
\end{array}\right.
\]
Even in this very simple case it can be shown that $\sCSP{\Gamma}$ is NP-hard, by reduction
from the {\sc Minimum 3-terminal Cut} problem~\shortcite{Dahlhaus94:multiterminalcut}.
An instance of this problem consists of an undirected graph $(V,E)$ in which each edge $e \in E$ has an associated weight,
together with a set of distinguished vertices, $\{v_1,v_2,v_3\} \subseteq V$, known as {\em terminals}.
The problem is to find a set of edges
with the smallest possible total weight whose removal disconnects each possible pair of terminals.
Such a set is known as a {\em minimum 3-terminal cut}.

To obtain the reduction to $\sCSP{\Gamma}$, let $I$ be an instance of
{\sc Minimum 3-Terminal Cut} consisting of the
graph \tuple{V,E} with terminals $\{v_1,v_2,v_3\}$.
We construct a corresponding instance $\P_I$ of $\sCSP{\Gamma}$ as follows.
The variables of $\P_I$ correspond to the set of vertices $V$.
For each edge $\{v_i,v_j\} \in E$, add a binary soft constraint with scope $\tuple{v_i,v_j}$
and evaluation function $\phi_{EQ}$, as above.
Finally, for each terminal $v_i \in \{v_1,v_2,v_3\}$, add a unary constraint
on the variable $v_i$ with evaluation function $\psi_i$, defined as follows:
\[
\psi_i(x) = \left\{\begin{array}{ll}
0\ & \text{if}\ x = i\\
|E|+1  & \text{otherwise}
\end{array}\right.
\]
It is straightforward to check that the number of edges in a minimum 3-terminal cut of $I$
is equal to the evaluation of a solution to $\P_I$.
\end{example}
%
The examples above indicate that generalizing the constraint satisfaction framework
to include soft constraints does indeed increase the computational complexity, in general.
For example, the standard {\sc 2-Satisfiability} problem is tractable, but the
soft constraint satisfaction problem involving only the single
binary Boolean function, $\phi_{XOR}$, defined at the end of Example~\ref{ex-Boolean}, is NP-hard.
Similarly, the standard constraint satisfaction problem involving only crisp unary constraints
and equality constraints is clearly trivial, but the
soft constraint satisfaction problem involving only soft unary constraints
and a soft version of the equality constraint, specified by the function $\phi_{EQ}$
defined in Example~\ref{ex-ternary}, is NP-hard.

However, in the next two sections we will show that it is possible to identify a large
class of functions for which the corresponding soft constraint satisfaction problem
is tractable.

\section{Generalized Interval Functions}

We begin with a rather restricted class of binary functions, with a very special structure.
%
\begin{definition}
\label{def:gif}
Let $D$ be a totally ordered set. A binary function, $\phi: D^2 \rightarrow E$
will be called a {\em generalized interval function} on $D$
if it has the following form:
\[
\phi(x,y) = \left\{\begin{array}{ll}
0 &\text{if }\  (x < a) \vee (y > b);\\
\rho &\text{otherwise}
\end{array}\right.
\]
for some $a,b \in D$ and some $\rho \in E$.
Such a function will be denoted \GIF{\rho}{a}{b}.
\end{definition}
%
We can explain the choice of name for these functions by
considering the unary function $\GIF{\rho}{a}{b}(x,x)$.
This function returns the value $\rho$ if and only if
its argument lies in the interval $[a,b]$;
outside of this interval it returns the value 0.

We shall write $\Gamma_{GI}$ to denote the set of all generalized interval functions on $D$,
where $D = \{1,2,\ldots,M\}$ with the usual ordering.

Note that the table of values for any function $\GIF{\rho}{a}{b} \in \Gamma_{GI}$
can be written as an \mbox{$M \times M$} matrix in which all the entries are 0, except for
the rectangular region lying between positions $\tuple{a,1}$ and $\tuple{M.b}$, where the entries have value $\rho$,
as illustrated in Figure~\ref{fig:GIF}.
Hence when $\rho = \infinity$, a soft constraint with evaluation function $\GIF{\rho}{a}{b}$ is equivalent to
a crisp constraint which is a particular form of {\em connected row-convex} constraint~\shortcite{Deville99:connectedrowconvex}.
%
\begin{figure}
\begin{center}
\begin{tabular}{ccc}
 & & {\Large $y$} \\
 \\
 & & $\left.~~ \begin{array}{ccccc} 1 & \cdots & b & b+1 \cdots & M \end{array} \right.$ \\
 \\
{\Large $x$} &
$\begin{array}{c}
1\\
\vdots \\
a-1\\
a\\
\vdots \\
M
\end{array}$
&
$\left( \begin{array}{cccccc}
0      & \cdots                   & 0      & ~~0  & \cdots              & 0 \\
\vdots & \raisebox{0.2ex}{0}      & \vdots & ~~\vdots & \raisebox{0.2ex}{0} & \vdots \\
0      & \cdots                   & 0      & ~~0      & \cdots              & 0 \\
\rho   & \cdots                   & \rho   & ~~0      & \cdots              & 0 \\
\vdots & \raisebox{0.5ex}{$\rho$} & \vdots & ~~\vdots & \raisebox{0.2ex}{0} & \vdots \\
\rho   & \cdots                   & \rho   & ~~0      & \cdots              & 0 \\
\end{array}
\right)$
\end{tabular}
\end{center}
\caption{The table of values for the function $\GIF{\rho}{a}{b}$}
\label{fig:GIF}
\end{figure}

The main result of this section is Corollary~\ref{complexity}, which states
that $\sCSP{\Gamma_{GI}}$ is tractable.
To establish this result we first define a weighted directed
graph\footnote{This construction was inspired by a
similar construction for certain Boolean constraints described by~\shortciteA{Khanna00:approximability}.}
associated with each instance of $\sCSP{\Gamma_{GI}}$ (see Figure~\ref{MF-EXfig}).

\begin{definition}
\label{MF-CONS}
Let $\P = \tuple{V,\{1,\ldots,M\},C}$ be an instance of $\sCSP{\Gamma_{GI}}$.
We define the weighted directed graph $\MF{\P}$ as follows.
\begin{itemize}
\item
The vertices of $\MF{\P}$ are as follows:
$
\{S,T\} \cup \{v_d \mid v \in V,\ d \in \{0,1,\ldots,M\}\}.
$
\item
The edges of $\MF{\P}$ are defined as follows:
\begin{itemize}
\item For each $v \in V$, there is an edge from $S$ to $v_M$ with weight $\infinity$;
\item For each $v \in V$, there is an edge from $v_0$ to $T$ with weight $\infinity$;
\item For each $v \in V$ and each $d \in \{1,2,\ldots,M-2\}$,
there is an edge from $v_{d}$ to $v_{d+1}$ with weight $\infinity$;
\item For each constraint $\tuple{\tuple{v,w},\GIF{\rho}{a}{b}} \in C$,
there is an edge from $w_b$ to $v_{a-1}$ with weight $\rho$.
These edges are called ``constraint edges".
\end{itemize}
\end{itemize}
\end{definition}

\begin{figure}[hbt]
% \centerline{\input{MaxFlow.pstex_t}}
\centerline{\epsfig{file=MaxFlow.eps,width=0.9\columnwidth}}
\caption{The graph $\MF{\P}$ associated with the instance $\P$ defined in Example~\ref{MF-EX}.\quad \quad \quad
(Note that solid arrows indicate edges with infinite weight.)} \label{MF-EXfig}
\end{figure}

\begin{example}
\label{MF-EX}
Let $\P = \tuple{\{x,y,z\},\{1,2,3,4\},C}$ be an instance of $\sCSP{\Gamma_{GI}}$
with the following four constraints:
\[
\begin{array}{l}
c_1 = \tuple{\tuple{y,x},\GIF{3}{3}{4}}\\[0.3cm]
c_3 = \tuple{\tuple{z,y},\GIF{7}{1}{3}}\\[0.3cm]
c_2 = \tuple{\tuple{y,z},\GIF{2}{4}{3}}\\[0.3cm]
c_4 = \tuple{\tuple{z,z},\GIF{\infinity}{2}{4}}
\end{array}
\]
The corresponding weighted directed graph $\MF{\P}$, is shown in Figure~\ref{MF-EXfig}.
\end{example}
%
Any set of edges $C$ in the graph $\MF{\P}$ whose removal leaves the vertices
$S$ and $T$ disconnected will be called a {\em cut}.
If $C$ is a minimal set of edges with this property, in the sense that removing any edge from $C$
leaves a set of edges which is not a cut, then $C$ will called a {\em minimal cut}.
If every edge in $C$ is a constraint edge, then $C$ will be called a {\em proper cut}.
The {\em weight} of a cut $C$ is defined to be the sum of the weights of all the edges in $C$.
%
\begin{example}
Consider the graph $\MF{\P}$ shown in Figure~\ref{MF-EXfig}.
The set $\{\tuple{y_3,z_0}\}$ is a proper cut in $\MF{\P}$ with weight 7,
which is minimal in the sense defined above.
The set $\{\tuple{x_4,y_2},\tuple{z_3,y_3}\}$ is also a proper cut in $\MF{\P}$ with weight 5,
which is again minimal in the sense defined above.
\end{example}
%
\newpage
\begin{proposition}
\label{the-MFreduction}
Let $\P$ be any instance of $\sCSP{\Gamma_{GI}}$,
and let $\MF{\P}$ be the associated weighted directed graph, as specified in Definition~\ref{MF-CONS}.
\begin{enumerate}
\item
For each minimal proper cut in $\MF{\P}$ with weight $\Phi$,
there is an assignment for $\P$ with evaluation $\Phi$.
\item
For each assignment $t$ for $\P$ with evaluation $\Phi$,
there is a proper cut in $\MF{\P}$ with weight $\Phi$.
\end{enumerate}
\end{proposition}
%
\begin{proof}
\begin{enumerate}
\item
Let $C$ be any minimal proper cut of the graph $\MF{\P}$,
and let $C_S$ be the component of $\MF{\P} \setminus C$ connected to $S$.
Since $C$ is proper, $C_S$ always contains $v_M$, and never contains $v_0$,
so we can define the assignment $t_C$ as follows:
\[
t_C(v) = \min \{d \mid v_d \in C_S\}
\]
By the construction of $\MF{\P}$, it follows that:
\begin{equation}
\label{eq:component}
t_C(v) > d \quad \Leftrightarrow \quad v_d \not \in C_S
\end{equation}
Now consider any constraint
$c=\tuple{\tuple{v,w},\GIF{\rho}{a}{b}}$ of $\P$, and its associated edge $e$ in $\MF{\P}$.
By Definition~\ref{def:gif} and Equation~\ref{eq:component},
\mbox{$\GIF{\rho}{a}{b}(t_C(v),t_C(w)) = \rho$} if and only if
$v_{a-1} \not \in C_S$ and $w_b \in C_S$, and hence if and only if
$e$ joins a vertex in $C_S$ to a vertex not in $C_S$.
Since $C$ is minimal, this happens if and only if $e \in C$.
Hence, the total weight of the cut $C$ is equal to the evaluation of $t_C$.

\item
Conversely, let $t$ be an assignment to $\P$,
and let $K$ be the set of constraints in $\P$ with a non-zero evaluation on $t$.

Now consider any path from $S$ to $T$ in $\MF{\P}$.
If we examine, in order, the constraint edges of this path, and assume that
each of the corresponding constraints evaluates to 0, then we obtain a
sequence of assertions of the following form:
\[
\begin{array}{rcll}
(v_{i_0} > M)   &\vee& (v_{i_1} < a_1) \\
(v_{i_1} > b_2) &\vee& (v_{i_2} < a_2) & \text{for some}\ b_2 \ge a_1 \\
% \vdots & \vdots \\
% v_{i_{s-1}} > b_s &\vee& v_{i_s} < a_s & \text{for some}\ b_s \ge a_{s-1} \\
          & \vdots \\
(v_{i_{k-1}} > b_{k}) &\vee& (v_{i_{k}} < a_{k}) & \text{for some}\ b_{k} \ge a_{k-1} \\
(v_{i_{k}} > b_{k+1}) &\vee& (v_{i_{k+1}} < 1)   & \text{for some}\ b_{k+1} \ge a_{k}
\end{array}
\]
Since the second disjunct of each assertion contradicts the first disjunct of the next,
these assertions cannot all hold simultaneously, so one of the corresponding constraints
must in fact give a non-zero evaluation on $t$.
Hence, every path from $S$ to $T$ includes at least one edge
corresponding to a constraint from $K$,
and so the edges corresponding to the set $K$ form a cut in $\MF{\P}$.
Furthermore, by the choice of $K$, the weight of this cut is equal to the evaluation of $t$.
\end{enumerate}
\end{proof}
%
Hence, by using a standard efficient algorithm for the
{\sc Minimum Weighted Cut} problem~\shortcite{Goldberg88:maxflow},
we can find an optimal assignment in cubic time, as the next result indicates.
%
\begin{corollary}
\label{complexity}
The time complexity of $\sCSP{\Gamma_{GI}}$ is $O(n^3|D|^3)$, where $n$ is the number of variables.
\end{corollary}
%
\begin{proof}
Let $\P = \tuple{V,D,C}$ be any instance of $\sCSP{\Gamma_{GI}}$,
and let $\MF{\P}$ be the corresponding weighted directed graph.
If the minimum weight for a cut in $\MF{\P}$ is $\omega < \infinity$, then it must be a proper cut,
so $\P$ has a solution with evaluation $\omega$, by Proposition~\ref{the-MFreduction}.
Moreover, if
the minimum weight for a cut in $\MF{\P}$ is $\infinity$, then the evaluation of every
assignment for $\P$ is $\infinity$.

Hence we have established
a linear-time reduction from $\sCSP{\Gamma_{GI}}$
to the {\sc Minimum Weighted Cut} problem.

Since $\MF{\P}$ has $v = |V|(|D|+1) + 2$ vertices, and the time complexity of
{\sc Minimum Weighted Cut} is
$O(v^3)$~\shortcite{Goldberg88:maxflow},
the result follows.
\end{proof}


\section{Submodular Functions}

In this section we will consider a rather more general and useful class of functions,
as described by~\shortciteA{Topkis78:submodular}.
%
\begin{definition}
\label{subModularDef}
Let $D$ be a totally ordered set. A function, $\phi: D^k \rightarrow E$
is called a {\em submodular function} on $D$ if,
for all $\tuple{a_1,\ldots,a_k},\tuple{b_1,\ldots,b_k}\in D^k$, we have
\begin{eqnarray*}
\phi(\min(a_1,b_1),\ldots,\min(a_k,b_k)) & + & \phi(\max(a_1,b_1),\ldots,\max(a_k,b_k)) ~~~~~~~~~~~ \\
                                         &   & ~~~~~~~ \leq \ \phi(a_1,\ldots,a_k)\ \ \ +\ \ \ \phi(b_1,\ldots,b_k).
\end{eqnarray*}
\end{definition}
%
It is easy to check that all unary functions and all generalized interval functions
are submodular.
It also follows immediately from Definition~\ref{subModularDef} that
the sum of any two submodular functions is submodular.
This suggests that in some cases it may be possible to express a
submodular function as a sum of simpler submodular functions. For example,
for any unary function $\psi: D \rightarrow E$ we have
\[
\psi(x) \equiv \sum_{d \in D} \GIF{\psi(d)}{d}{d}(x,x).
\]
For binary functions, the definition of submodularity can be
expressed in a simplified form, as follows.
%
\begin{remark}
\label{rem:binarysub}
Let $D$ be a totally ordered set. A binary function, $\phi: D^2 \rightarrow E$
is submodular if and only if,
for all $u,v,x,y \in D$, with $u \leq x$ and $v \leq y$, we have:
\[
\phi(u,v) + \phi(x,y) \le \phi(u,y) + \phi(x,v)
\]
Note that when $u = x$ or $v=y$ this inequality holds trivially, so it is sufficient to check only those cases where
$u < x$ and $v<y$.
\end{remark}
%
\begin{example}
\label{ex:prod}
Let $D$ be the set $\{1,2,\ldots,M\}$ with the usual ordering, and consider the binary
function $\pi_M$, defined by $\pi_M(x,y) = M^2 - xy$.

For any $u,v,x,y \in D$, with $u < x$ and $v < y$, we have:
{\small
\begin{eqnarray*}
\pi_M(u,v) + \pi_M(x,y) & = & 2 M^2 - uv - xy \\
                        & = & 2 M^2 - uy - xv - (x-u)(y-v)\\
                        & \leq & \pi_M(u,y) + \pi_M(x,v).
\end{eqnarray*}
}
Hence, by Remark~\ref{rem:binarysub}, the function $\pi_M$ is submodular.
\end{example}
%
A real-valued $m \times n$ matrix $A$ with the property that
\[
A_{uv} + A_{xy} \leq A_{uy} + A_{xv}, \quad \quad \mbox{for all $1 \leq u < x \leq m$, \ $1 \leq v < y \leq n$}
\]
is known in operational research as a {\em Monge matrix}
(for a survey of the properties of such matrices and their use in optimization, see~\shortciteR{Burkard96:Mongesurvey}).
It is clear from Remark~\ref{rem:binarysub} that the table of values for a real-valued binary submodular function is a Monge matrix,
and conversely, every square Monge matrix can be viewed as a table of values for a binary submodular function.

It was shown by~\shortciteA{Rudolf95:Monge} that an arbitrary Monge matrix can be decomposed as a sum of simpler matrices.
We now obtain a corresponding result for binary submodular functions, by showing that
any binary submodular function can be decomposed as a sum of
generalized interval functions. (The result we obtain below is slightly more general than the decomposition result for
Monge matrices given by~\shortciteA{Rudolf95:Monge}, because we are allowing submodular functions to take infinite values.)
Using this decomposition result, we will show that the set of unary and binary submodular functions
is a tractable soft constraint language.

To obtain our decomposition  result, we use the following technical lemma.
%
\begin{lemma}
\label{indLemma}
Let $D$ be a totally ordered set and let \mbox{$\phi:D^2\rightarrow E$}
be a binary submodular function.
%
For any $a,b,c \in D$ such that $a \le b \le c$,
if there exists $e \in D$ with $\phi(e,b) = 0$,
then for all $x \in D$ we have \mbox{$\phi(x,b) \le \max(\phi(x,a),\phi(x,c))$}.
\end{lemma}
%
\begin{proof}
Assume that $\phi(e,b) = 0$.
\begin{itemize}
\item
If $x > e$ then, by the submodularity of $\phi$, we have
$\phi(x,b) \le \phi(x,b) + \phi(e,a) \le \phi(x,a) + \phi(e,b) = \phi(x,a)$
\item
If $x < e$ then, by the submodularity of $\phi$, we have
$\phi(x,b) \le \phi(x,b) + \phi(e,c) \le \phi(e,b) + \phi(x,c) = \phi(x,c)$.
\item
If $e=x$ then $\phi(x,b) = 0$.
\end{itemize}
Hence, in all cases the result holds.
\end{proof}
%
\begin{lemma}
\label{mainDecomp}
Let $D$ be a totally ordered finite set. A binary function, $\phi: D^2 \rightarrow E$
is submodular if and only if it can be expressed as a sum of generalized interval functions on $D$.
Furthermore, a decomposition of this form can be obtained in $O(|D|^3)$ time.
\end{lemma}
%
\begin{proof}
By the observations already made, any function $\phi$
which is equal to a sum of generalized interval functions is clearly submodular.

To establish the converse,
we use induction on the {\em tightness} of $\phi$, denoted $\tau(\phi)$,
that is, the number of pairs for which the value of $\phi$ is non-zero.

Assume that $\phi$ is a binary submodular function.
If $\tau(\phi) = 0$, then $\phi$ is identically zero, so the result holds trivially.
Otherwise, by induction, we shall assume that the result holds
for all binary submodular functions that have a lower tightness.

To simplify the notation, we shall assume that $D = \{1,2,\ldots,M\}$, with the usual ordering.

We will say that a value $a \in D$ is
{\em inconsistent} if, for all $y \in D$, $\phi(a,y) = \infinity$.
If every $a\in D$ is inconsistent, then all values of $\phi$ are $\infinity$,
so it is equal to the generalized interval function $\GIF{\infinity}{1}{M}$,
and the result holds.
Otherwise, if there exists at least one inconsistent value,
then we can find a pair of values $a,b \in D$, with $|a-b| = 1$, such that
$a$ is inconsistent and $b$ is not inconsistent.

Now define the function $\phi'$ as follows:
\[
\phi'(x,y) = \left\{\begin{array}{ll}
\phi(x,y) & \text{if} \ x \neq a\\
\phi(b,y) & \text{if} \ x = a
\end{array}\right.
\]
It is straightforward to check that $\phi'$ is submodular
and $\phi(x,y) = \phi'(x,y) + \GIF{\infinity}{a}{a}(x,x)$.
Since $\tau(\phi') \le \tau(\phi)$, it now suffices to show that
the result holds for $\phi'$.

By repeating this procedure we may assume that $\phi$ has no
inconsistent values, and by symmetry, that the reversed function $\phi^T$,
defined by $\phi^T(x,y) = \phi(y,x)$, also has no inconsistent values.

We will say that a value $a \in D$ is
{\em penalized} if, for all $y \in D$, $\phi(a,y) > 0$.
If $a$ is penalized, then we set $\mu_a = \min \{\phi(a,y)| y \in D\}$.
If $\mu_a = \infinity$, then $a$ is inconsistent, so we may assume that $\mu_a < \infinity$,
and define a new function $\phi'$ as follows:
\[
\phi'(x,y) = \left\{\begin{array}{ll}
\phi(x,y)         & \text{if} \ x \neq a\\
\phi(x,y) - \mu_a & \text{if} \ x = a.
\end{array}\right.
\]
Again it is straightforward to check that $\phi'$ is submodular
and $\phi(x,y) = \phi'(x,y) + \GIF{\mu_a}{a}{a}(x,x)$.
Since $\tau(\phi') \le \tau(\phi)$, it now suffices to show that
the result holds for $\phi'$.

By repeating this procedure we may assume that neither $\phi$ nor
$\phi^T$ has any inconsistent or penalized values.

Now if, for all $a,b \in D$, we have $\phi(a,M) = \phi(M,b) = 0$,
then, by submodularity, for all $a,b, \in D$, $\phi(a,b) = \phi(a,b) + \phi(M,M) \le \phi(a,M) + \phi(M,b) = 0$,
so $\phi$ is identically 0, and the result holds trivially.
Otherwise, by symmetry, we can choose $a$ to be the largest value in $D$
such that $\phi(a,M) \neq 0$.
Since $a$ is not penalized, we can
then choose $r$ to be the largest value in $D$ such that $\phi(a,r) = 0$.
By the choice of $a$, we know that $r < M$, and so we can define $b = r + 1$.
This situation is illustrated in Figure~\ref{mainProofFig}.

\begin{figure*}[bt]
\centerline{\input{reduction.pstex_t}}

\caption{(a) The choice of $a$ and $b$ in the proof of
Theorem~\ref{mainDecomp}. Dotted lines represent known $0$
values of $\phi$. Solid lines represent values of $\phi$ known not to be $0$.\hspace{2cm}
(b-d) Representations of the three cases for the choice of $u,v,x,y$. The filled
area represents the non-zero values of the generalized interval constraint subtracted from $\phi$ to obtain $\phi'$.}
\label{mainProofFig}
\end{figure*}

For any $x,y \in D$ such that $x \le a$ and $y \ge b$, we have:
{\small
\[
\begin{array}{rcll}
\phi(x,y) & =   & \phi(x,y) + \phi(a,r)                 & \text{($\phi(a,r) = 0$)}\\
          & \ge & \phi(x,r) + \phi(a,y)                 & \text{(submodularity)}\\
          & =   & \phi(x,r) + \max(\phi(a,y),\phi(a,r)) & \text{($\phi(a,r) = 0$)}\\
          & \ge & \phi(x,r) + \phi(a,b)                 & \text{(Lemma~\ref{indLemma})}\\
          & \ge & \phi(a,b)
\end{array}
\]
}
%
Hence we can now define a function $\phi'$ as follows:
\[
\phi'(x,y) = \left\{\begin{array}{ll}
\phi(x,y)             & \text{if}\ x > a \vee y < b\\
0                     & \text{if}\ x = a \wedge y = b\\
\phi(x,y) - \phi(a,b) & \text{otherwise.}
\end{array}\right.
\]
It is straightforward to check that
$\phi(x,y) = \phi'(x,y) + \GIF{\phi(a,b)}{b}{a}(y,x)$.
Since $\tau(\phi') < \tau(\phi)$, it only remains to show that
$\phi'$ is submodular, and then the result follows by induction.
In other words, it suffices to show that for any $u,v,x,y \in D$ such that $u<x$ and $v<y$, we have:
\begin{equation}
\phi'(u,v) + \phi'(x,y) \le \phi'(u,y) + \phi'(x,v)
\label{equationTwo}
\end{equation}
%
Replacing $x$ with $u$ in the inequality derived above, we have that whenever $u \le a$ and $y \ge b$,
\begin{equation}
\phi(u,y) \ge \phi(u,r) + \phi(a,b).
\label{equationOne}
\end{equation}
%
The proof of inequality~(\ref{equationTwo}) may be divided into four cases,
depending on the values of $\phi(a,b)$ and the choice of $u,v,x,y$:
%
\begin{enumerate}
\item $\phi(a,b) = \infinity$

In this case, $\phi'$ differs from $\phi$ only on the pair \tuple{a,b} (because $\infinity - \infinity = \infinity$).
Since $\phi$ is submodular, inequality~(\ref{equationTwo})
can only fail to hold if either \tuple{x,v} or \tuple{u,y} equals \tuple{a,b}.

If $\tuple{x,v} = \tuple{a,b}$, then, using inequality~(\ref{equationOne}),
we know that $\phi(u,y)=\infinity$, so $\phi'(u,y)=\infinity - \infinity = \infinity$,
and inequality~(\ref{equationTwo}) holds.

If $\tuple{u,y} = \tuple{a,b}$ then we have, for all $x > u$ and $y > v$,
\[
\begin{array}{rcll}
\lefteqn{\phi'(u,v) + \phi'(x,y) \ = \ \phi(u,v) + \phi(x,y)} ~~~~~~~~ \\
& \le & \phi(u,v) + \max(\phi(x,r),\phi(x,M)) & \text{(by Lemma~\ref{indLemma})}\\
& =   & \phi(u,v) + \phi(x,r)                 & \text{($x > a \Rightarrow \phi(x,M)=0$)}\\
& \le & \phi(u,r) + \phi(x,v)                 & \text{(by submodularity)}\\
& =   & \phi(x,v)                             & \text{(since $\phi(u,r) = 0$)}\\
& =   & \phi'(x,v)\\
& \le & \phi'(u,y) + \phi'(x,v)
\end{array}
\]
so inequality~(\ref{equationTwo}) holds.

\item $a<u<x$ or $v<y<b$; \ (see Figure~\ref{mainProofFig} part (b))

In this situation we know that inequality~(\ref{equationTwo}) holds
because $\phi$ and $\phi'$ are identical for these arguments.

\item $u < x \le a$ or $b \le v<y$; \ (see Figure~\ref{mainProofFig} part (c))

If $u < x \le a$, then we have:
\begin{eqnarray*}
\phi'(u,v) & = & \phi(u,v) -  \rho\\
\phi'(x,v) & = & \phi(x,v) -  \rho\\
\phi'(u,y) & = & \phi(u,y) -  \rho'\\
\phi'(x,y) & = & \phi(x,y) -  \rho'
\end{eqnarray*}
where $\rho$ and $\rho'$ are either $0$ or $\phi(a,b)$, depending on whether
$v$ or $y$ are less than $b$.  Inequality~(\ref{equationTwo}) follows
trivially by cancelling $\rho$ or $\rho'$ or both.

An exactly similar argument holds if $b \le v<y$.

\item $u \le a<x$ and $v<b \le y$; \ (see Figure~\ref{mainProofFig} part (d))

If $u < a$, than by inequality~(\ref{equationOne}) we have
$\phi(u,y) - \phi(a,b) \ge \phi(u,r)$, so $\phi'(u,y) \ge \phi(u,r)$.
Moreover, if $u = a$, then $\phi(u,r) = 0$, so again $\phi'(u,y) \ge \phi(u,r)$.
Hence,
\[
\begin{array}{rcll}
\lefteqn{\phi'(u,v) + \phi'(x,y) \ = \ \phi(u,v) + \phi(x,y)} ~~~~~~~ \\
& \le & \phi(u,v) + \max(\phi(x,r),\phi(x,M)) & \text{(by Lemma~\ref{indLemma})}\\
& =   & \phi(u,v) + \phi(x,r)                 & \text{($x > a \Rightarrow \phi(x,M)=0$)}\\
& \le & \phi(u,r) + \phi(x,v)                 & \text{(by submodularity)}\\
& \le & \phi'(u,y) + \phi(x,v)                & \text{(since $\phi'(u,y) \ge \phi(u,r)$)}\\
& \le & \phi'(u,y) + \phi'(x,v)
\end{array}
\]
so again inequality~(\ref{equationTwo}) holds.
\end{enumerate}
%
Hence, in all cases inequality~(\ref{equationTwo}) holds, so $\phi'$ is submodular, and the result follows by induction.

The number of generalized interval functions in the decomposition of a binary submodular function
can grow quadratically with $|D|$ (see Example~\ref{ex:pidecomp} below) and the cost of subtracting one
binary submodular function from another is also quadratic in $|D|$. Hence a naive algorithm to obtain such a
decomposition by calculating the required generalized interval functions and subtracting off each one in turn
from the original function will take $O(|D|^4)$ time.
However, by taking advantage of the simple structure of generalized interval functions,
it is possible to obtain a suitable decomposition in $O(|D|^3)$ time; a possible algorithm is given in Figure~\ref{fig:decompalgo}.
The correctness of this algorithm follows directly from the proof of the decomposition result given above.
%
\begin{figure}[hbt]
{\small
\begin{tabbing}
{\bf Output:} \= A set \kill % Set the tab stop
{\bf Input:}  \> A binary submodular function $\phi$ on the set \{1,2,\ldots,M\}\\
              \> such that neither $\phi$ nor $\phi^T$ has any inconsistent or penalized values\\
\\
{\bf Output:} \> A set of generalized interval functions $\{\phi_1,\phi_2,\ldots,\phi_q\}$\\
              \> such that $ \phi(x,y) = \sum_{i=1}^q \phi_i(x,y)$ \\
\\
{\bf Algorithm:}\\
\\
{\bf for} \= $i = 1$ \= {\bf to} $M, \ \mu[i] = \min\{\phi(i,j) \mid j=1,2,\ldots,M\}$ \= \% Calculate row minima \kill
% \\
% {\bf for} \> $i = 2$ {\bf to} $M, \ \ ${\bf if} $(\mu[i] = \infty) \wedge (\mu[i-1] < \infty)$ {\bf then}  \>\> \% Clear inconsistent rows\\
%           \> {\bf output} $\GIF{\infty}{i}{i}(x,x)$\\
%           \> {\bf for} $j = 1$ {\bf to} $M, \ \ \phi(i,j) = \phi(i-1,j)$\\
%           \> $\mu[i] = \mu[i-1]$\\
% {\bf for} \> $i = M-1$ {\bf downto} $1, \ \ ${\bf if} $(\mu[i] = \infty) \wedge (\mu[i+1] < \infty)$ {\bf then}\\
%           \> {\bf output} $\GIF{\infty}{i}{i}(x,x)$\\
%           \> {\bf for} $j = 1$ {\bf to} $M, \ \ \phi(i,j) = \phi(i+1,j)$\\
%           \> $\mu[i] = \mu[i+1]$\\
% {\bf if} $\mu[1] = \infty$ {\bf then stop}\\
% \\
% {\bf for} \> $i = 1$ {\bf to} $M, \ \ ${\bf if} $(\mu[i] > 0)$ {\bf then}  \>\> \% Clear penalized rows\\
%           \> {\bf output} $\GIF{\mu[i]}{i}{i}(x,x)$\\
%           \> {\bf for} $j = 1$ {\bf to} $M, \ \ \phi(i,j) = \phi(i,j) - \mu[i]$\\
% \\
{\bf for} \> $j = 1$ {\bf to} $M, \ \ T[j] = 0$                                    \>\> \% Initialise list of values to be subtracted\\
{\bf for} \> $i = M$ {\bf downto} $1$                                              \>\> \% For each row\ldots\\
          \> {\bf while} $\phi(i,M) > T[M]$ \ {\bf do}                             \>\> \% If $\phi(i,M)$ not yet zero\ldots\\
          \>             \> $j = M$; \ {\bf while} $\phi(i,j) > T[j]$ \ {\bf do} $j = j-1$ \> \% Find maximal zero position in row $i$\\
          \>             \> $\Delta = \phi(i,j+1) - T[j+1]$                                \> \% Set new value to be subtracted \\
          \>             \> {\bf output} $\GIF{\Delta}{j+1}{i}(y,x)$                     \> \% Output generalized interval function\\
          \>             \> {\bf for} $k = j+1$ {\bf to} $M, \ \ \ T[k] = T[k] + \Delta$ \> \% Update list of values to be subtracted \\
          \> {\bf for} $j = 1$ {\bf to} $M, \ \ \phi(i,j) = \phi(i,j) - T[j]$            \>\> \% Subtract values from this row\\
\\
{\bf for} \> $i = 1$ {\bf to} $M, \ \ T[j] = 0$                                    \>\> \% Initialise list of values to be subtracted\\
{\bf for} \> $j = M$ {\bf downto} $1$                                              \>\> \% For each column\ldots\\
          \> {\bf while} $\phi(M,j) > T[M]$ \ {\bf do}                             \>\> \% If $\phi(M,j)$ not yet zero\ldots\\
          \>             \> $i = M$; \ {\bf while} $\phi(i,j) > T[i]$ \ {\bf do} $i = i-1$ \> \% Find maximal zero position in column $j$\\
          \>             \> $\Delta = \phi(i+1,j) - T[i+1]$                                \> \% Set new value to be subtracted \\
          \>             \> {\bf output} $\GIF{\Delta}{i+1}{j}(x,y)$                     \> \% Output generalized interval function\\
          \>             \> {\bf for} $k = i+1$ {\bf to} $M, \ \ \ T[k] = T[k] + \Delta$ \> \% Update list of values to be subtracted \\
          \> {\bf for} $i = 1$ {\bf to} $M, \ \ \phi(i,j) = \phi(i,j) - T[i]$            \>\> \% Subtract values from this column
\end{tabbing}
}
\caption{A decomposition algorithm with time complexity $O(|D|^3)$}
\label{fig:decompalgo}
\end{figure}
\end{proof}
%
\begin{example}
\label{ex:pidecomp}
Consider the binary function $\pi_M$ on $D = \{1,2,\ldots,M\}$, defined in Example~\ref{ex:prod}.
When $M = 3$, the values of $\pi_3$ are given by the following table:
\[
\begin{array}{c|ccc}
\pi_3 & 1 & 2 & 3 \\
\hline
1 & 8 & 7 & 6 \\
2 & 7 & 5 & 3 \\
3 & 6 & 3 & 0
\end{array}
\]
Note that:
%
{\small
\begin{eqnarray*}
\lefteqn{
\left(
\begin{array}{ccc}
8 & 7 & 6 \\
7 & 5 & 3 \\
6 & 3 & 0
\end{array}
\right)
=
}
\\
& &
\left(
\begin{array}{ccc}
6 & 6 & 6 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
0 & 0 & 0 \\
3 & 3 & 3 \\
0 & 0 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
2 & 0 & 0 \\
2 & 0 & 0 \\
2 & 0 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
0 & 1 & 0 \\
0 & 1 & 0 \\
0 & 1 & 0
\end{array}
\right)
\\
& &
~ +
\left(
\begin{array}{ccc}
0 & 0 & 0 \\
1 & 1 & 0 \\
1 & 1 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
0 & 0 & 0 \\
0 & 0 & 0 \\
1 & 1 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
0 & 0 & 0 \\
1 & 0 & 0 \\
1 & 0 & 0
\end{array}
\right)
+
\left(
\begin{array}{ccc}
0 & 0 & 0 \\
0 & 0 & 0 \\
1 & 0 & 0
\end{array}
\right).
\end{eqnarray*}
}
%
Hence,
{\small
\begin{eqnarray*}
\pi_3(x,y) & = &
\GIF{6}{1}{1}(x,x) + \GIF{3}{2}{2}(x,x) + \GIF{2}{1}{1}(y, y) + \GIF{1}{2}{2}(y,y) \\
& & ~ + \GIF{1}{2}{2}(x,y) + \GIF{1}{3}{2}(x,y) + \GIF{1}{2}{1}(x,y) + \GIF{1}{3}{1}(x,y).
\end{eqnarray*}
}
In general, for arbitrary values of $M$, we have
\[
\pi_M(x,y) = \sum_{d=1}^{M-1} \left( \GIF{M (M-d)}{d}{d}(x,x) + \GIF{M-d}{d}{d}(y,y) + \sum_{e=1}^{M-1} \GIF{1}{d+1}{e}(x,y) \right)
\]
We remark that this decomposition is not unique - other decompositions exist,
including the symmetric decomposition
% $\pi_3(x,y) = \pi'_3(x,y) + \pi'_3(y,x)$, where
% {\small
% \begin{eqnarray*}
% \pi'_3(x,y) & = & \GIF{4}{1}{1}(x,x) + \GIF{\frac{5}{2}}{2}{2}(x,x) + \\
%               & & \GIF{\frac{1}{2}}{2}{1}(x,y) + \GIF{\frac{1}{2}}{3}{2}(x,y) + \GIF{1}{3}{1}(x,y).
% \end{eqnarray*}
% }
$\pi_M(x,y) = \pi'_M(x,y) + \pi'_M(y,x)$, where
\[
\pi'_M(x,y) = \sum_{d=1}^{M-1} \left( \GIF{\frac{(M^2-d^2)}{2}}{d}{d}(x,x) + \GIF{\frac{1}{2}}{d+1}{d}(x,y) + \sum_{e=1}^{d-1} \GIF{1}{d+1}{e}(x,y) \right)
\]
\end{example}
%
Combining Lemma~\ref{mainDecomp} with Corollary~\ref{complexity}, gives:
%
\begin{theorem}
\label{tractableClass}
For any finite soft constraint language $\Gamma$ on a finite totally ordered set $D$,
if $\Gamma$ contains only unary or binary submodular functions,
then the time complexity of $\sCSP{\Gamma}$ is $O(n^3 |D|^3)$.
\end{theorem}
%
\omitted{
We note that the result given in Theorem~\ref{mainDecomp} relies on the
fact that we are assuming that the evaluations lie in a set with a
(partial) subtraction operation.
If we relax this assumption, then it is possible to construct
submodular functions which are not expressible as the sum of generalized
interval functions, as the next example demonstrates.
%
\begin{example}
Consider the binary function illustrated in Figure~\ref{noRedFig}.
\begin{figure}[htbp]
\centerline{\input{nored.pstex_t}}
\caption{An example of a binary function which is submodular if
the aggregation operator is $x \oplus y = \text{min}\{5,x+y\}$,
but which is not expressible as a sum of generalized interval functions.}
\label{noRedFig}
\end{figure}

This function is submodular when the aggregation operator for the evaluations,
$\oplus$, is defined by $x \oplus y = \min(5,x+y)$, but it
cannot be expressed as a sum of generalised interval functions.
\end{example}
}
%
The next result shows that the tractable class identified in Theorem~\ref{tractableClass}
is maximal.
%
\begin{theorem}
\label{the:maximal}
Let $\Gamma$ be the set of all binary submodular functions on a totally ordered finite set $D$,
with $|D| \geq 2$.
%
For any binary function $\psi \not \in \Gamma$, $\sCSP{\Gamma\cup\{\psi\}}$ is NP-hard.
\end{theorem}

\begin{proof}
We shall give a reduction
from $\sCSP{\{\phi_{XOR}\}}$ to $\sCSP{\Gamma\cup\{\psi\}}$, where
$\phi_{XOR}$ is the binary function defined in Example~\ref{ex-Boolean}.
It was pointed out in Example~\ref{ex-Boolean} that $\sCSP{\{\phi_{XOR}\}}$
corresponds to the {\sc Max-Sat} problem for the exclusive-or predicate,
which is known to be NP-hard~\shortcite{Creignouetal:siam01}.
Hence $\sCSP{\Gamma\cup\{\psi\}}$ is also NP-hard.

To simplify the notation, we shall assume that $D = \{1,2,\ldots,M\}$, with the usual ordering.

Since $\psi$ is not submodular, there exist $a,b,c,d\in D$ such that
$a < b$ and $c < d$ but $\psi(a,c) + \psi(b,d) > \psi(a,d) + \psi(b,c)$.

Choose an arbitrary evaluation $\epsilon$ such that $0 < \epsilon < \infinity$, and define $\lambda$ and $\mu$ as follows:
\begin{eqnarray*}
\lambda & = & \min(\psi(a,c), \psi(a,d)+ \psi(b,c) + \epsilon) \\
\mu     & = & \min(\psi(b,d), \psi(a,d)+ \psi(b,c) + \epsilon)
\end{eqnarray*}
It is straightforward to check that
\begin{equation}
\label{lambdaMuInequality}
\psi(a,d) + \psi(b,c) < \lambda + \mu < \infinity.
\end{equation}

Now define a binary function $\zeta$ as follows:
\[
\zeta(x,y) = \left\{\begin{array}{ll}
\mu          &\text{if}\  (x,y)=(1,a)\\
\lambda      &\text{if}\  (x,y)=(2,b)\\
\infinity    &\text{otherwise}
\end{array}
\right.
\]
and a binary function $\phi$ as follows:
\[
\phi(x,y) = \left\{\begin{array}{ll}
0             & \text{if}\  (x,y)=(c,1)\\
\psi(a,d) + 1 & \text{if}\  (x,y)=(c,2)\\
\psi(b,c) + 1 & \text{if}\  (x,y)=(d,1)\\
0             & \text{if}\  (x,y)=(d,2)\\
\infinity     & \text{otherwise}
\end{array}
\right.
\]
It is straightforward to check that both $\zeta$ and $\phi$ are submodular.

Now consider the instance $\P_0$ of $\sCSP{\Gamma\cup\{\psi\}}$
illustrated in Figure~\ref{xorFig}.
%
\begin{figure}[htbp]
\centerline{\input{XorGadget.pstex_t}}

\caption{An instance of $\sCSP{\Gamma\cup\{\psi\}}$
used to construct a specific soft constraint between variables $x$ and $y$.}
\label{xorFig}
\end{figure}
%
It is simple but tedious to verify that the combined effect of the six soft constraints
shown in Figure~\ref{xorFig} on the variables $x$ and $y$ is equivalent to
imposing a soft constraint on these variables with evaluation function $\chi$,
defined as follows:
\[
\chi(x,y) = \left\{\begin{array}{ll}
\lambda + \mu + \lambda + \mu         & \text{if}\  x,y \in \{1,2\} \text{ and } x = y\\
\lambda + \mu + \psi(a,d) + \psi(b,c) & \text{if}\  x,y \in \{1,2\} \text{ and } x \neq y\\
\infinity & \text{otherwise}
\end{array}\right.
\]
Note that, by inequality~(\ref{lambdaMuInequality}),
we have $\lambda + \mu + \psi(a,d) + \psi(b,c) < \lambda + \mu + \lambda + \mu < \infinity$.

% By using the ``gadget'' shown in Figure~\ref{xorFig}, we can
% effectively "simulate" the binary function $\phi_{XOR}$ defined in Example~\ref{ex-Boolean},
% and hence construct a reduction
% from $\sCSP{\{\phi_{XOR}\}}$ to $\sCSP{\Gamma\cup\{\psi\}}$, as required.
%
Now let $\P$ be any instance of $\sCSP{\{\phi_{XOR}\}}$.
If we replace each constraint
$\tuple{\tuple{x,y},\phi_{XOR}}$ in $\P$ with the set of constraints shown in Figure~\ref{xorFig}
(introducing fresh variables $t,u,v,w$ each time)
then we obtain an instance $\P'$ of $\sCSP{\Gamma\cup\{\psi\}}$.
It is straightforward to check that $\P'$ has a solution involving only the values $1$ and $2$,
and that such solutions correspond exactly to the solutions of $\P$, so this construction
gives a polynomial-time reduction from $\sCSP{\{\phi_{XOR}\}}$ to $\sCSP{\Gamma\cup\{\psi\}}$, as required.
\end{proof}



\section{Applications}
\label{sec-applications}

In this section we give a number of examples to illustrate the wide range of
soft constraints which can be shown to be tractable using the results
obtained in the previous sections.

First we define a standard way to associate a function with a given relation.
%
\begin{definition}
\label{defAssociatedFunction}
For any $k$-ary relation $R$ on a set $D$,  we define an {\em associated function},
$\phi_R : D^k \rightarrow E$, as follows:
\[
\phi_R(x_1,x_2,\ldots,x_k) = \left\{\begin{array}{ll}
0         &\text{if}\  \tuple{x_1,x_2,\ldots,x_k} \in R\\
\infinity &\text{otherwise.}
\end{array}
\right.
\]
\end{definition}
%
By Theorem~\ref{tractableClass},
any collection of crisp constraints, where each constraint is specified by a relation $R$ for which $\phi_R$ is
unary or binary submodular, can be solved in cubic time, even when combined with
other soft constraints that are also unary or binary submodular.
%
\begin{example}
\label{exCHIP}
The constraint programming language CHIP incorporates a
number of constraint solving techniques for arithmetic and other constraints.
In particular, it provides a
constraint solver for a restricted class of crisp constraints
over natural numbers,
referred to as {\em basic constraints}~\shortcite{vanHentenryck92:generic}.
These basic constraints are of two kinds, which are referred to as
``domain constraints'' and ``arithmetic constraints''.
The domain constraints
described by~\shortciteA{vanHentenryck92:generic}
are unary constraints which restrict the value of a variable to some
specified finite subset of the natural numbers. The arithmetic constraints
described by~\shortciteA{vanHentenryck92:generic} have one of the following forms:
\[
\begin{array}{ll}
aX \neq b       & \hspace*{1cm} aX \leq bY + c \\
aX = bY + c     & \hspace*{1cm} aX \geq bY + c
\end{array}
\]
where variables are represented by upper-case letters, and
constants by lower case letters, all constants are non-negative real numbers
and $a$ is non-zero.

For each of these crisp constraints the associated function given by
Definition~\ref{defAssociatedFunction} is unary or binary submodular,
hence, by Corollary~\ref{complexity},
any problem involving constraints of this form can be solved in cubic time.
Moreover, any other soft constraints with unary or binary submodular evaluation functions
can be added to such problems without sacrificing tractability
(including the examples below).
\end{example}
%
Now assume, for simplicity, that $D = \{1,2,\ldots,M\}$.
%
\begin{example}
Consider the binary linear function $\lambda$ defined by
$\lambda(x,y) = ax + by + c$, where $a,b\in \mathbb{R}^+$.

This function is submodular and hence, by Corollary~\ref{complexity}, any collection of such
binary linear soft constraints over the discrete set $D$
can be solved in cubic time.
\end{example}
%
\begin{example}
The Euclidean length function $\sqrt{x^2 + y^2}$ is submodular,
and can be used to express the constraint that a 2-dimensional point $\tuple{x,y}$ is
``as close to the origin as possible''.
\end{example}
%
\begin{example}
\label{closePossible}
The following functions are all submodular:
\begin{itemize}
\item $\delta_r(x,y) = |x-y|^r$, where $r \in \mathbb{R}$, $r \ge 1$.

The function $\delta_r$ can be used to express the
constraint that:
``The values assigned to the variables $x$ and $y$ should be as similar as possible''.
\item $\delta^+_r(x,y) = (\max(x-y,0))^r$, where $r\in \mathbb{R}$, $r \ge 1$.

The function $\delta^+_r$ can be used to express the constraint that:
``The value of $x$ is either less than or as near as possible to $y$''.
\item $
\delta^{\geq}_r(x,y) =
\mbox{
$
\left\{\begin{array}{ll}
|x-y|^r   & \text{if}\ x \ge y\\
\infinity & \text{otherwise}
\end{array}\right.
$
}
$
where $r \in \mathbb{R}$, $r \ge 1$.

The function $\delta^{\geq}_r$ can be used to express the temporal constraint that:
``$x$ occurs as soon as possible after $y$''.
\end{itemize}
\end{example}
%
\begin{example}
\label{ex:optim2}
Reconsider the optimization problem defined in Example~\ref{ex:optim}.
Since $\psi_i$ is unary, and $\delta_r$ is binary submodular (Example~\ref{closePossible}),
this problem can be solved in cubic time, using the methods developed in this paper.

Let $\P$ be the instance with $n=3$ and $r=2$. The values of $\delta_2$ are given by the following table:
\[
\begin{array}{c|ccc}
\delta_2 & 1 & 2 & 3 \\
\hline
1 & 0 & 1 & 4 \\
2 & 1 & 0 & 1 \\
3 & 4 & 1 & 0
\end{array}
\]
Hence,
{\small
\begin{eqnarray*}
\delta_2(x,y)
& = & \GIF{1}{3}{2}(y,x) + \GIF{1}{2}{1}(y,x) + \GIF{2}{3}{1}(y,x)\\
&   & ~ + \GIF{1}{3}{2}(x,y) + \GIF{1}{2}{1}(x,y) + \GIF{2}{3}{1}(x,y)
\end{eqnarray*}
}
Using this decomposition for $\delta_2$, we can construct the graph $\MF{\P}$ corresponding to the instance $\P$, as
shown in Figure~\ref{fig:exoptim2}.
\begin{figure}[bht]
\centerline{\epsfig{file=MaxFlow2.eps,width=1.02\columnwidth }}
\caption{The graph $\MF{\P}$ associated with the instance $\P$ defined in Example~\ref{ex:optim2}.}
\label{fig:exoptim2}
\end{figure}


The minimum weight of any cut in this graph is $\frac{11}{4}$, and hence the optimal evaluation of any assignment for $\P$ is
$\frac{11}{4}$.

One of the several possible cuts with this weight is indicated by the gray line across the
graph, which corresponds to the solution
% \[
% \begin{array}{cccccc}
% v_1 & v_2 & v_3 & v_4 & v_5 & v_6 \\
% 1   & 1   & 2   & 1   & 2   & 3
% \end{array}
% \]
\mbox{$v_1=1$}, \mbox{$v_2=1$}, \mbox{$v_3=2$}, \mbox{$v_4=2$}, \mbox{$v_5=3$}, \mbox{$v_6=3$}.
\end{example}

Note that some of the submodular functions defined in this section may appear to be similar to the soft simple temporal constraints
with semi-convex cost functions defined and shown to be tractable by~\shortciteA{Khatib01:temporal}.
However, there are fundamental differences: the constraints described by~\shortciteA{Khatib01:temporal} are defined over an infinite set of values,
and their tractability depends crucially on the aggregation operation used for the costs being {\em idempotent}
(i.e., the operation {\em min}). In this paper we are considering soft constraints over finite sets of values,
and an aggregation operation which is {\em strictly monotonic} (e.g., addition of real numbers), so our results
cannot be directly compared with those in the paper by~\shortciteA{Khatib01:temporal}.

% ----------------------------------------------------------------
\section{Conclusion}

As we have shown with a number of examples, the problem of identifying an optimal assignment for an arbitrary collection
of soft constraints is generally NP-hard. However, by making use of the notion of submodularity, we have
identified a large and expressive class of soft constraints for which this problem is tractable.
In particular, we have shown that {\em binary} soft constraints with the property of submodularity can be
solved in cubic time. By making use of this result, it should be possible to extend the range of optimisation
problems that can be effectively solved using constraint programming.

From a theoretical perspective, this paper gives the first complete characterisation of a tractable class of
soft constraints over a finite set of values with more than two elements. We are confident that the methods
developed here can be extended to identify other tractable cases, and hence to begin a systematic investigation
of the computational complexity of soft constraint satisfaction.
A first step in this direction has been taken by~\shortciteA{Cohen03:multimorphisms}.

We believe that this work illustrates once again the benefit of interaction between research on constraint satisfaction and more
traditional research on discrete optimization and mathematical programming: the notion of submodularity comes
from mathematical programming, but the idea of modelling problems with binary constraints over arbitrary finite domains
comes from constraint programming.
By combining these ideas, we obtain a flexible and powerful modelling language with a provably efficient solution strategy.

\section{Acknowledgments}

An earlier version
of this paper, omitting many of the proofs,
was presented at the International Joint Conference on Artificial Intelligence in 2003. This research was partially supported by the UK EPSRC grant
GR/R81213/01.

% ----------------------------------------------------------------
%\bibliography{csp}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Allen}{Allen}{1995}]{Allen94:natural}
Allen, J. \BBOP1995\BBCP.
\newblock {\Bem Natural Language Understanding --- 2nd Edition}.
\newblock The Benjamin/Cummings Publishing Company.

\bibitem[\protect\BCAY{Bistarelli, Montanari, Rossi, Schiex, Verfaillie,\ \BBA\ Fargier}{Bistarelli
  et~al.}{1999}]{Bistarelli99:semiringVCSP}
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., \BBA\ Fargier, H.\BBOP1999\BBCP.
\newblock \BBOQ Semiring-based {CSP}s and valued {CSP}s: Frameworks,
  properties, and comparison\BBCQ\
\newblock {\Bem Constraints}, {\Bem 4}, 199--240.

\bibitem[\protect\BCAY{Bulatov}{Bulatov}{2003}]{Bulatov03:conservative}
Bulatov, A.\BBOP2003\BBCP.
\newblock \BBOQ Tractable conservative constraint satisfaction problems\BBCQ\
\newblock In {\Bem Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science
({LICS}'03)}, \BPGS\ 321--330.

\bibitem[\protect\BCAY{Bistarelli, Montanari,\ \BBA\ Rossi}{Bistarelli
  et~al.}{1997}]{Bistarelli97:semiring}
Bistarelli, S., Montanari, U., \BBA\ Rossi, F. \BBOP1997\BBCP.
\newblock \BBOQ Semiring-based constraint satisfaction and optimisation\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 44}, 201--236.

\bibitem[\protect\BCAY{Burkard, Klinz,\ \BBA\ Rudolf}{Burkard
  et~al.}{1996}]{Burkard96:Mongesurvey}
Burkard, R., Klinz, B., \BBA\ Rudolf, R. \BBOP1996\BBCP.
\newblock \BBOQ Perspectives of {M}onge properties in optimization\BBCQ\
\newblock {\Bem Discrete Applied Mathematics}, {\Bem 70}, 95--161.

\bibitem[\protect\BCAY{Cohen, Cooper, Jeavons,\ \BBA\ Krokhin}{Cohen
  et~al.}{2003}]{Cohen03:multimorphisms}
Cohen, D., Cooper, M., Jeavons, P., \BBA\ Krokhin, A. \BBOP2003\BBCP.
\newblock \BBOQ Soft constraints: Complexity and multimorphisms\BBCQ\
\newblock In {\Bem Proceedings of 9th International Conference on Principles
  and Practice of Constraint Programming (CP'03)}, \lowercase{\BVOL}\ 2833 of
  {\Bem Lecture Notes in Computer Science}, \BPGS\ 244--258. Springer-Verlag.

\bibitem[\protect\BCAY{Cooper}{Cooper}{2003}]{Cooper03:reduction}
Cooper, M. \BBOP2003\BBCP.
\newblock \BBOQ Reduction operations in fuzzy or valued constraint satisfaction\BBCQ\
\newblock {\Bem Fuzzy Sets and Systems}, {\Bem 134}, 311--342.

\bibitem[\protect\BCAY{Creignou, Khanna,\ \BBA\ Sudan}{Creignou
  et~al.}{2001}]{Creignouetal:siam01}
Creignou, N., Khanna, S., \BBA\ Sudan, M. \BBOP2001\BBCP.
\newblock {\Bem Complexity Classifications of Boolean Constraint Satisfaction
  Problems}, \lowercase{\BVOL}~7 of {\Bem SIAM Monographs on Discrete
  Mathematics and Applications}.

\bibitem[\protect\BCAY{Dahlhaus, Johnson, Papadimitriou, Seymour,\ \BBA\
  Yannakakis}{Dahlhaus et~al.}{1994}]{Dahlhaus94:multiterminalcut}
Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., \BBA\ Yannakakis, M.
  \BBOP1994\BBCP.
\newblock \BBOQ The complexity of multiterminal cuts\BBCQ\
\newblock {\Bem {SIAM} Journal on Computing}, {\Bem 23\/}(4), 864--894.

\bibitem[\protect\BCAY{Deville, Barette,\ \BBA\
  van Hentenryck}{Deville et~al.}{1999}]{Deville99:connectedrowconvex}
Deville, Y., Barette, O., \BBA\ van Hentenryck, P. \BBOP1999\BBCP.
\newblock \BBOQ Constraint satisfaction over connected row convex constraints\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 109\/}, 243--271.

\bibitem[\protect\BCAY{Feder\ \BBA\ Vardi}{Feder\ \BBA\
  Vardi}{1998}]{Feder98:monotone}
Feder, T.\BBACOMMA\  \BBA\ Vardi, M. \BBOP1998\BBCP.
\newblock \BBOQ The computational structure of monotone monadic {SNP} and
  constraint satisfaction: A study through {D}atalog and group theory\BBCQ\
\newblock {\Bem {SIAM} Journal of Computing}, {\Bem 28}, 57--104.

\bibitem[\protect\BCAY{Freuder\ \BBA\ Wallace}{Freuder\ \BBA\
  Wallace}{1992}]{Freuder92:partial}
Freuder, E.\BBACOMMA\  \BBA\ Wallace, R. \BBOP1992\BBCP.
\newblock \BBOQ Partial constraint satisfaction\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 58}, 21--70.

\bibitem[\protect\BCAY{Fujishige}{Fujishige}{1991}]{Fujishige91:submodular}
Fujishige, S. \BBOP1991\BBCP.
\newblock {\Bem Submodular Functions and Optimization}, \lowercase{\BVOL}~47 of
  {\Bem Annals of Discrete Mathematics}.
\newblock North-Holland, Amsterdam.

\bibitem[\protect\BCAY{Goldberg\ \BBA\ Tarjan}{Goldberg\ \BBA\
  Tarjan}{1988}]{Goldberg88:maxflow}
Goldberg, A.\BBACOMMA\  \BBA\ Tarjan, R. \BBOP1988\BBCP.
\newblock \BBOQ A new approach to the maximum flow problem\BBCQ\
\newblock {\Bem Journal of the {ACM}}, {\Bem 35}, 921--940.

\bibitem[\protect\BCAY{Iwata, Fleischer,\ \BBA\ Fujishige}{Iwata
  et~al.}{2001}]{Iwata01:submodular}
Iwata, S., Fleischer, L., \BBA\ Fujishige, S. \BBOP2001\BBCP.
\newblock \BBOQ A combinatorial strongly polynomial algorithm for minimizing
  submodular functions\BBCQ\
\newblock {\Bem Journal of the {ACM}}, {\Bem 48}, 761--777.

\bibitem[\protect\BCAY{Jeavons, Cohen,\ \BBA\ Gyssens}{Jeavons
  et~al.}{1997}]{Jeavons97:closure}
Jeavons, P., Cohen, D., \BBA\ Gyssens, M. \BBOP1997\BBCP.
\newblock \BBOQ Closure properties of constraints\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 44}, 527--548.

\bibitem[\protect\BCAY{Kautz\ \BBA\ Selman}{Kautz\ \BBA\
  Selman}{1992}]{Kautz92:planning}
Kautz, H.\BBACOMMA\  \BBA\ Selman, B. \BBOP1992\BBCP.
\newblock \BBOQ Planning as satisfiability\BBCQ\
\newblock In {\Bem Proceedings of the Tenth European Conference on Artificial
  Intelligence ({ECAI}'92)}, \BPGS\ 359--363.

\bibitem[\protect\BCAY{Khanna, Sudan, Trevisan,\ \BBA\ Williamson}{Khanna
  et~al.}{2000}]{Khanna00:approximability}
Khanna, S., Sudan, M., Trevisan, L., \BBA\ Williamson, D. \BBOP2000\BBCP.
\newblock \BBOQ The approximability of constraint satisfaction problems\BBCQ\
\newblock {\Bem SIAM Journal on Computing}, {\Bem 30\/}(6), 1863--1920.

\bibitem[\protect\BCAY{Khatib, Morris, Morris,\ \BBA\ Rossi}{Khatib
  et~al.}{2001}]{Khatib01:temporal}
Khatib, L., Morris, P., Morris, R., \BBA\ Rossi, F. \BBOP2001\BBCP.
\newblock \BBOQ Temporal constraint reasoning with preferences\BBCQ\
\newblock In {\Bem {P}roceedings of the 17th {I}nternational {J}oint
  {C}onference on {A}rtificial {I}ntelligence (IJCAI-01)}, \BPGS\ 322--327,
  Seattle, USA.

\bibitem[\protect\BCAY{Larrosa, Meseguer,\ \BBA\ Schiex}{Larrosa
  et~al.}{1999}]{Larrosa99:reversible}
Larrosa, J., Meseguer, P., \BBA\ Schiex, T. \BBOP1999\BBCP.
\newblock \BBOQ Maintaining Reversible {DAC} for {Max-CSP}\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 107}(1), 149--163.

\bibitem[\protect\BCAY{Lov\'asz}{Lov\'asz}{1983}]{Lovasz83:submodular}
Lov\'asz, L. \BBOP1983\BBCP.
\newblock \BBOQ Submodular functions and convexity\BBCQ\
\newblock In Bachem, A., Gr\"otschel, M., \BBA\ Korte, B.\BEDS, {\Bem
  Mathematical Programming -- The State of the Art}, \BPGS\ 235–--257, Berlin.
  Springer-Verlag.

\bibitem[\protect\BCAY{Montanari}{Montanari}{1974}]{Montanari74:constraints}
Montanari, U. \BBOP1974\BBCP.
\newblock \BBOQ Networks of constraints: Fundamental properties and
  applications to picture processing\BBCQ\
\newblock {\Bem Information Sciences}, {\Bem 7}, 95--132.

\bibitem[\protect\BCAY{Nemhauser\ \BBA\ Wolsey}{Nemhauser\ \BBA\
  Wolsey}{1988}]{Nemhauser88:optimization}
Nemhauser, G.\BBACOMMA\  \BBA\ Wolsey, L. \BBOP1988\BBCP.
\newblock {\Bem Integer and Combinatorial Optimization}.
\newblock John Wiley \& Sons.

\bibitem[\protect\BCAY{Rosenfeld, Hummel\ \BBA\ Zucker}{Rosenfeld
   et~al.}{1976}]{Rosenfeld76:relaxation}
Rosenfeld, A., Hummel, R., \BBA\ Zucker, S. \BBOP1976\BBCP.
\newblock \BBOQ Scene labeling by relaxation operations\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man and Cybernetics}, {\Bem 6},
  420--433.

\bibitem[\protect\BCAY{Rudolf\ \BBA\ Woeginger}{Rudolf\ \BBA\
  Woeginger}{1995}]{Rudolf95:Monge}
Rudolf, R.\BBACOMMA\  \BBA\ Woeginger, G. \BBOP1995\BBCP.
\newblock \BBOQ The cone of {M}onge matrices: extremal rays and
  applications\BBCQ\
\newblock {\Bem ZOR -- Mathematical Methods of Operations Research}, {\Bem 42},
  161--168.

\bibitem[\protect\BCAY{Ruttkay}{Ruttkay}{1994}]{Ruttkay94:fuzzy}
Ruttkay, Z. \BBOP1994\BBCP.
\newblock \BBOQ Fuzzy constraint satisfaction\BBCQ\
\newblock In {\Bem Proceedings 3rd {IEEE} International Conference on Fuzzy
  Systems}, \BPGS\ 1263--1268.

\bibitem[\protect\BCAY{Schaefer}{Schaefer}{1978}]{Schaefer78:complexity}
Schaefer, T. \BBOP1978\BBCP.
\newblock \BBOQ The complexity of satisfiability problems\BBCQ\
\newblock In {\Bem Proceedings 10th {ACM} Symposium on Theory of Computing,
  {STOC'78}}, \BPGS\ 216--226.

\bibitem[\protect\BCAY{Schrijver}{Schrijver}{2000}]{Schrijver00:submodular}
Schrijver, A. \BBOP2000\BBCP.
\newblock \BBOQ A combinatorial algorithm minimizing submodular functions in
  strongly polynomial time\BBCQ\
\newblock {\Bem Journal of Combinatorial Theory, Series B}, {\Bem 80},
  346--355.

\bibitem[\protect\BCAY{Topkis}{Topkis}{1978}]{Topkis78:submodular}
Topkis, D. \BBOP1978\BBCP.
\newblock \BBOQ Minimizing a submodular function on a lattice\BBCQ\
\newblock {\Bem Operations Research}, {\Bem 26}, 305--321.

\bibitem[\protect\BCAY{Topkis}{Topkis}{1998}]{Topkis98:supermodular}
Topkis, D. \BBOP1998\BBCP.
\newblock {\Bem Supermodularity and Complementarity}.
\newblock Princeton University Press.

\bibitem[\protect\BCAY{van Beek}{van Beek}{1992}]{vanBeek92:temporal}
van Beek, P. \BBOP1992\BBCP.
\newblock \BBOQ Reasoning about qualitative temporal information\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 58}, 297--326.

\bibitem[\protect\BCAY{van Hentenryck, Deville,\ \BBA\ Teng}{van Hentenryck
  et~al.}{1992}]{vanHentenryck92:generic}
van Hentenryck, P., Deville, Y., \BBA\ Teng, C.-M. \BBOP1992\BBCP.
\newblock \BBOQ A generic arc-consistency algorithm and its
  specializations\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 57}, 291--321.

\end{thebibliography}
\end{document}
% ----------------------------------------------------------------
